Submission #71519869

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/segtree>
typedef long long ll;
using namespace std;

int op(int x, int y) {return max(x,y);}
int e() {return 0;}

const int nmax = 2e5 + 10;
int P[nmax];
int Q[nmax];
atcoder::segtree<int, op, e> Pseg(nmax);

ll fun(int l, int r){
    if(r-l <= 1) return 0;
    
    int s = Q[Pseg.prod(l, r)];

    ll ans = 0;
    if(s != l){
        ans = max(ans, fun(l, s) + s - Q[Pseg.prod(l, s)]);
    }

    if(s+1 != r){
        ans = max(ans, fun(s+1, r) + Q[Pseg.prod(s+1, r)] - s);
    }

    // cout << l << " " << r << endl;
    // cout << "ans=" << ans << endl;
    // cout << "s=" << s << endl;

    return ans;

}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> P[i];
        P[i]--;
        Q[P[i]] = i;
        Pseg.set(i, P[i]);
    }

    cout << fun(0, n) << endl;

}

Submission Info

Submission Time
Task F - Cat exercise
User sakimori_coder
Language C++23 (GCC 15.2.0)
Score 550
Code Size 897 Byte
Status AC
Exec Time 74 ms
Memory 19528 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 550 / 550
Status
AC × 2
AC × 40
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 3 ms 5964 KiB
example_01.txt AC 3 ms 5968 KiB
hand_00.txt AC 69 ms 19400 KiB
hand_01.txt AC 74 ms 19528 KiB
hand_02.txt AC 68 ms 13128 KiB
hand_03.txt AC 70 ms 18180 KiB
hand_04.txt AC 55 ms 13136 KiB
hand_05.txt AC 3 ms 5848 KiB
hand_06.txt AC 3 ms 6060 KiB
hand_07.txt AC 41 ms 6868 KiB
random_00.txt AC 48 ms 6836 KiB
random_01.txt AC 50 ms 6924 KiB
random_02.txt AC 49 ms 6920 KiB
random_03.txt AC 49 ms 6916 KiB
random_04.txt AC 48 ms 7036 KiB
random_05.txt AC 47 ms 7104 KiB
random_06.txt AC 49 ms 6976 KiB
random_07.txt AC 49 ms 7100 KiB
random_08.txt AC 48 ms 6872 KiB
random_09.txt AC 48 ms 7044 KiB
random_10.txt AC 59 ms 11528 KiB
random_11.txt AC 58 ms 10696 KiB
random_12.txt AC 52 ms 7680 KiB
random_13.txt AC 56 ms 9728 KiB
random_14.txt AC 69 ms 15752 KiB
random_15.txt AC 49 ms 6956 KiB
random_16.txt AC 49 ms 7360 KiB
random_17.txt AC 53 ms 9100 KiB
random_18.txt AC 50 ms 8048 KiB
random_19.txt AC 51 ms 8748 KiB
random_20.txt AC 50 ms 8380 KiB
random_21.txt AC 54 ms 9440 KiB
random_22.txt AC 49 ms 7612 KiB
random_23.txt AC 53 ms 9020 KiB
random_24.txt AC 51 ms 7752 KiB
random_25.txt AC 56 ms 9812 KiB
random_26.txt AC 48 ms 6996 KiB
random_27.txt AC 50 ms 8540 KiB
random_28.txt AC 50 ms 7772 KiB
random_29.txt AC 49 ms 7492 KiB