oj.uz

Submission #803996

# Submission time Handle Problem Language Result Execution time Memory
803996 2023-08-03T06:48:43 Z guagua0407 Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 62 ms 31784 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

const int mxn=2e5+5;
int num[mxn];
pair<int,int> table[20][mxn];

ll cal(int l,int r){
    if(l==r) return 0;
    int p=__lg(r-l+1);
    int node=max(table[p][l],table[p][r+1-(1<<p)]).s;
    int leftnode=-1,rightnode=-1;
    if(node>l){
        p=__lg(node-l);
        leftnode=max(table[p][l],table[p][node-(1<<p)]).s;
    }
    if(node<r){
        p=__lg(r-node);
        rightnode=max(table[p][node+1],table[p][r+1-(1<<p)]).s;
    }
    //cout<<l<<' '<<r<<' '<<leftnode<<' '<<node<<' '<<rightnode<<'\n';
    if(leftnode!=-1 and rightnode!=-1){
        return max(cal(l,node-1)+1ll*(node-leftnode),cal(node+1,r)+1ll*(rightnode-node));
    }
    else if(leftnode!=-1){
        return cal(l,node-1)+1ll*(node-leftnode);
    }
    else{
        return cal(node+1,r)+1ll*(rightnode-node);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
        table[0][i]={num[i],i};
        num[i]--;
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
    }
    for(int i=1;i<20;i++){
        for(int j=0;j+(1<<i)<=n;j++){
            table[i][j]=max(table[i-1][j],table[i-1][j+(1<<(i-1))]);
        }
    }
    cout<<cal(0,n-1)<<'\n';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 936 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 936 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 2 ms 852 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 936 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 50 ms 30568 KB Output is correct
26 Correct 53 ms 31784 KB Output is correct
27 Correct 61 ms 31780 KB Output is correct
28 Correct 56 ms 30540 KB Output is correct
29 Correct 55 ms 30632 KB Output is correct
30 Correct 61 ms 30652 KB Output is correct
31 Correct 62 ms 30648 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 936 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 2 ms 852 KB Output isn't correct
27 Halted 0 ms 0 KB -