답안 #916505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916505	2024-01-26T03:02:25 Z	Darren0724	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	39 ms	40896 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=200005;
const int K=18;
int n;
vector<int> v(N);
int cmp(int i,int j){
    return (v[i]>v[j]?i:j);
}
struct sparse_table{
    vector<vector<int>> mx;
    void init(){
        mx.resize(K,vector<int>(N));
        for(int i=0;i<n;i++){
            mx[0][i]=i;
        }
        for(int i=1;i<K;i++){
            for(int j=0;j+(1<<i)<=n;j++){
                mx[i][j]=cmp(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int ask(int l,int r){
        int p=__lg(r-l);
        return cmp(mx[p][l],mx[p][r-(1<<p)]);
    }
}sp;

int dc(int l,int r,int rec){
    if(r<=l){
        return 0;
    }
    int p=sp.ask(l,r);
    if(rec==-1)rec=p;
    return abs(rec-p)+max(dc(l,p,p),dc(p+1,r,p));
}


int32_t main(){
    abcorz;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sp.init();
    int ans=dc(0,n,-1);
    cout<<ans<<endl;

    return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct
11	Correct	12 ms	31580 KB	Output is correct
12	Correct	13 ms	31580 KB	Output is correct
13	Correct	13 ms	31580 KB	Output is correct
14	Correct	13 ms	31580 KB	Output is correct
15	Correct	12 ms	31580 KB	Output is correct
16	Correct	12 ms	31580 KB	Output is correct
17	Correct	12 ms	31576 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct
11	Correct	12 ms	31580 KB	Output is correct
12	Correct	13 ms	31580 KB	Output is correct
13	Correct	13 ms	31580 KB	Output is correct
14	Correct	13 ms	31580 KB	Output is correct
15	Correct	12 ms	31580 KB	Output is correct
16	Correct	12 ms	31580 KB	Output is correct
17	Correct	12 ms	31576 KB	Output is correct
18	Correct	12 ms	31836 KB	Output is correct
19	Correct	13 ms	31836 KB	Output is correct
20	Correct	13 ms	31832 KB	Output is correct
21	Correct	14 ms	31832 KB	Output is correct
22	Correct	13 ms	31836 KB	Output is correct
23	Correct	13 ms	31836 KB	Output is correct
24	Correct	13 ms	31836 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct
11	Correct	12 ms	31580 KB	Output is correct
12	Correct	13 ms	31580 KB	Output is correct
13	Correct	13 ms	31580 KB	Output is correct
14	Correct	13 ms	31580 KB	Output is correct
15	Correct	12 ms	31580 KB	Output is correct
16	Correct	12 ms	31580 KB	Output is correct
17	Correct	12 ms	31576 KB	Output is correct
18	Correct	12 ms	31836 KB	Output is correct
19	Correct	13 ms	31836 KB	Output is correct
20	Correct	13 ms	31832 KB	Output is correct
21	Correct	14 ms	31832 KB	Output is correct
22	Correct	13 ms	31836 KB	Output is correct
23	Correct	13 ms	31836 KB	Output is correct
24	Correct	13 ms	31836 KB	Output is correct
25	Correct	12 ms	31580 KB	Output is correct
26	Incorrect	17 ms	31956 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct
11	Correct	12 ms	31580 KB	Output is correct
12	Correct	13 ms	31580 KB	Output is correct
13	Correct	13 ms	31580 KB	Output is correct
14	Correct	13 ms	31580 KB	Output is correct
15	Correct	12 ms	31580 KB	Output is correct
16	Correct	12 ms	31580 KB	Output is correct
17	Correct	12 ms	31576 KB	Output is correct
18	Correct	12 ms	31836 KB	Output is correct
19	Correct	13 ms	31836 KB	Output is correct
20	Correct	13 ms	31832 KB	Output is correct
21	Correct	14 ms	31832 KB	Output is correct
22	Correct	13 ms	31836 KB	Output is correct
23	Correct	13 ms	31836 KB	Output is correct
24	Correct	13 ms	31836 KB	Output is correct
25	Correct	37 ms	40896 KB	Output is correct
26	Correct	37 ms	40124 KB	Output is correct
27	Correct	39 ms	39992 KB	Output is correct
28	Correct	35 ms	33112 KB	Output is correct
29	Correct	36 ms	33368 KB	Output is correct
30	Correct	35 ms	33016 KB	Output is correct
31	Correct	35 ms	33132 KB	Output is correct

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31632 KB	Output is correct
2	Incorrect	13 ms	31576 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	31580 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31652 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	12 ms	31576 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31576 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31580 KB	Output is correct
11	Correct	12 ms	31580 KB	Output is correct
12	Correct	13 ms	31580 KB	Output is correct
13	Correct	13 ms	31580 KB	Output is correct
14	Correct	13 ms	31580 KB	Output is correct
15	Correct	12 ms	31580 KB	Output is correct
16	Correct	12 ms	31580 KB	Output is correct
17	Correct	12 ms	31576 KB	Output is correct
18	Correct	12 ms	31836 KB	Output is correct
19	Correct	13 ms	31836 KB	Output is correct
20	Correct	13 ms	31832 KB	Output is correct
21	Correct	14 ms	31832 KB	Output is correct
22	Correct	13 ms	31836 KB	Output is correct
23	Correct	13 ms	31836 KB	Output is correct
24	Correct	13 ms	31836 KB	Output is correct
25	Correct	12 ms	31580 KB	Output is correct
26	Incorrect	17 ms	31956 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

답안 #916505

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0