답안 #916507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916507	2024-01-26T03:04:59 Z	Darren0724	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	38 ms	39476 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 cnt1=0;
int dc(int l,int r,int rec){
    if(r<=l){
        return 0;
    }
    cnt1++;
    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);
    assert(cnt1<=n);
    cout<<ans<<endl;

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31596 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31608 KB	Output is correct
6	Correct	13 ms	31580 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31580 KB	Output is correct
9	Correct	13 ms	31580 KB	Output is correct
10	Correct	13 ms	31580 KB	Output is correct
11	Correct	15 ms	31900 KB	Output is correct
12	Correct	12 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	13 ms	31640 KB	Output is correct
16	Correct	13 ms	31832 KB	Output is correct
17	Correct	13 ms	31580 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31596 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31608 KB	Output is correct
6	Correct	13 ms	31580 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31580 KB	Output is correct
9	Correct	13 ms	31580 KB	Output is correct
10	Correct	13 ms	31580 KB	Output is correct
11	Correct	15 ms	31900 KB	Output is correct
12	Correct	12 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	13 ms	31640 KB	Output is correct
16	Correct	13 ms	31832 KB	Output is correct
17	Correct	13 ms	31580 KB	Output is correct
18	Correct	12 ms	31580 KB	Output is correct
19	Correct	12 ms	31580 KB	Output is correct
20	Correct	13 ms	31576 KB	Output is correct
21	Correct	13 ms	31576 KB	Output is correct
22	Correct	13 ms	31580 KB	Output is correct
23	Correct	13 ms	31580 KB	Output is correct
24	Correct	12 ms	31580 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31596 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31608 KB	Output is correct
6	Correct	13 ms	31580 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31580 KB	Output is correct
9	Correct	13 ms	31580 KB	Output is correct
10	Correct	13 ms	31580 KB	Output is correct
11	Correct	15 ms	31900 KB	Output is correct
12	Correct	12 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	13 ms	31640 KB	Output is correct
16	Correct	13 ms	31832 KB	Output is correct
17	Correct	13 ms	31580 KB	Output is correct
18	Correct	12 ms	31580 KB	Output is correct
19	Correct	12 ms	31580 KB	Output is correct
20	Correct	13 ms	31576 KB	Output is correct
21	Correct	13 ms	31576 KB	Output is correct
22	Correct	13 ms	31580 KB	Output is correct
23	Correct	13 ms	31580 KB	Output is correct
24	Correct	12 ms	31580 KB	Output is correct
25	Correct	13 ms	31576 KB	Output is correct
26	Incorrect	13 ms	31688 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31596 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31608 KB	Output is correct
6	Correct	13 ms	31580 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31580 KB	Output is correct
9	Correct	13 ms	31580 KB	Output is correct
10	Correct	13 ms	31580 KB	Output is correct
11	Correct	15 ms	31900 KB	Output is correct
12	Correct	12 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	13 ms	31640 KB	Output is correct
16	Correct	13 ms	31832 KB	Output is correct
17	Correct	13 ms	31580 KB	Output is correct
18	Correct	12 ms	31580 KB	Output is correct
19	Correct	12 ms	31580 KB	Output is correct
20	Correct	13 ms	31576 KB	Output is correct
21	Correct	13 ms	31576 KB	Output is correct
22	Correct	13 ms	31580 KB	Output is correct
23	Correct	13 ms	31580 KB	Output is correct
24	Correct	12 ms	31580 KB	Output is correct
25	Correct	38 ms	39476 KB	Output is correct
26	Correct	37 ms	38668 KB	Output is correct
27	Correct	37 ms	38728 KB	Output is correct
28	Correct	38 ms	31580 KB	Output is correct
29	Correct	36 ms	31728 KB	Output is correct
30	Correct	35 ms	31580 KB	Output is correct
31	Correct	34 ms	31580 KB	Output is correct

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31596 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31608 KB	Output is correct
6	Correct	13 ms	31580 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31580 KB	Output is correct
9	Correct	13 ms	31580 KB	Output is correct
10	Correct	13 ms	31580 KB	Output is correct
11	Correct	15 ms	31900 KB	Output is correct
12	Correct	12 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	13 ms	31640 KB	Output is correct
16	Correct	13 ms	31832 KB	Output is correct
17	Correct	13 ms	31580 KB	Output is correct
18	Correct	12 ms	31580 KB	Output is correct
19	Correct	12 ms	31580 KB	Output is correct
20	Correct	13 ms	31576 KB	Output is correct
21	Correct	13 ms	31576 KB	Output is correct
22	Correct	13 ms	31580 KB	Output is correct
23	Correct	13 ms	31580 KB	Output is correct
24	Correct	12 ms	31580 KB	Output is correct
25	Correct	13 ms	31576 KB	Output is correct
26	Incorrect	13 ms	31688 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

답안 #916507

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