Task: | Vaihdot |
Sender: | Lieska |
Submission time: | 2020-09-06 12:04:51 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 23 |
#3 | ACCEPTED | 64 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 2, 3 | details |
#10 | ACCEPTED | 0.02 s | 2, 3 | details |
#11 | ACCEPTED | 0.02 s | 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 2, 3 | details |
#13 | ACCEPTED | 0.02 s | 2, 3 | details |
#14 | ACCEPTED | 0.02 s | 2, 3 | details |
#15 | ACCEPTED | 0.02 s | 2, 3 | details |
#16 | ACCEPTED | 0.02 s | 2, 3 | details |
#17 | ACCEPTED | 0.11 s | 3 | details |
#18 | ACCEPTED | 0.19 s | 3 | details |
#19 | ACCEPTED | 0.09 s | 3 | details |
#20 | ACCEPTED | 0.09 s | 3 | details |
#21 | ACCEPTED | 0.10 s | 3 | details |
#22 | ACCEPTED | 0.12 s | 3 | details |
#23 | ACCEPTED | 0.18 s | 3 | details |
#24 | ACCEPTED | 0.20 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:94:30: warning: unused variable 'b' [-Wunused-variable] ll a=v[i][si-1], b=v[i+1].size(); ^
Code
#include <bits/stdc++.h>using namespace std;typedef long long ll;ll t[555050], t1[202020], r[202020], M, h[202020][3][3], s[202020][3][3], s1[202020][4][3], n;vector<ll> p[202020], l[202020], v[202020];ll test(){ll x=0;for (ll i=1; i<=2*M+2; ++i) t[i]=0;for (ll i=1; i<=n; ++i){for (auto u:p[i]) {ll a=u+M-1;while (a>0){t[a]--;a/=2;}}for (auto u:l[i]){ll a=u+M-1;while (a>0){t[a]++;a/=2;}}if (h[i][1][1]){ll a=h[i][1][1]+M-1, b=h[i][1][2]+M-1;while (a<=b){if (a%2==1){x+=t[a];a++;}if (b%2==0){x+=t[b];b--;}a/=2;b/=2;}}if (h[i][2][1]){ll a=h[i][2][1]+M-1, b=h[i][2][2]+M-1;while (a<=b){if (a%2==1){x+=t[a];a++;}if (b%2==0){x+=t[b];b--;}a/=2;b/=2;}}}return x;}int main(){cin >> n;M=1;while ((n+2)>M) M*=2;for (ll i=1; i<=n; ++i){ll a;cin >> a;t1[i]=a;r[a]=i;}ll k=1;for (ll i=1; i<=n; ++i){if (r[i]<r[i-1]) k++;v[k].push_back(r[i]);}for (ll i=1; i<=k; ++i){ll si=v[i].size();if (i!=1){ll a=v[i][0], b=v[i-1].size();if (si==1){if (v[i-1][b-1]!=n){s[a][1][1]=v[i-1][b-1]+1;s[a][1][2]=n;}}else{if (v[i-1][b-1]<(v[i][1]-1)){s[a][1][1]=v[i-1][b-1]+1;s[a][1][2]=v[i][1]-1;}}}if (i!=k){ll a=v[i][si-1], b=v[i+1].size();if (si==1){if (v[i+1][0]!=1){s[a][2][1]=1;s[a][2][2]=v[i+1][0]-1;}}else{if (v[i][si-2]<(v[i+1][0]-1)){s[a][2][1]=v[i][si-2]+1;s[a][2][2]=v[i+1][0]-1;}}}for (ll j=0; j<si; ++j){ll a, b, c=v[i][j];if (j==0) a=1;else a=v[i][j-1]+1;if (j==(si-1)) b=n;else b=v[i][j+1]-1;if (a<=c && b>=c){if (a<c){s1[c][1][1]=a;s1[c][1][2]=c-1;}if (b>c){s1[c][2][1]=c+1;s1[c][2][2]=b;}}else{s1[c][1][1]=a;s1[c][1][2]=b;}if (j==0 && si!=1 && i!=1){int b=v[i-1].size();if (v[i-1][b-1]!=n){s1[c][3][1]=v[i-1][b-1]+1;s1[c][3][2]=n;}}if (j==si-1 && si!=1 && i!=k){if (v[i+1][0]!=1){s1[c][3][1]=1;s1[c][3][2]=v[i+1][0]-1;}}}}for (ll i=1; i<=n; ++i){if (s[i][1][1]){l[s[i][1][1]].push_back(i);p[s[i][1][2]+1].push_back(i);h[i][1][1]=s[i][1][1];h[i][1][2]=s[i][1][2];}if (s[i][2][1]){l[s[i][2][1]].push_back(i);p[s[i][2][2]+1].push_back(i);h[i][2][1]=s[i][2][1];h[i][2][2]=s[i][2][2];}}ll ans=test();if (ans){cout << k-2 << " " << ans/2 << "\n";return 0;}for (ll i=1; i<=n+1; ++i){while (l[i].size()) l[i].pop_back();while (p[i].size()) p[i].pop_back();h[i][1][1]=0;h[i][1][2]=0;h[i][2][1]=0;h[i][2][2]=0;}for (ll i=1; i<=n; ++i){if (s[i][1][1]){h[i][1][1]=s[i][1][1];h[i][1][2]=s[i][1][2];}if (s[i][2][1]){h[i][2][1]=s[i][2][1];h[i][2][2]=s[i][2][2];}if (s1[i][1][1]){l[s1[i][1][1]].push_back(i);p[s1[i][1][2]+1].push_back(i);}if (s1[i][2][1]){l[s1[i][2][1]].push_back(i);p[s1[i][2][2]+1].push_back(i);}if (s1[i][3][1]){l[s1[i][3][1]].push_back(i);p[s1[i][3][2]+1].push_back(i);}}ans=test();for (int i=1; i<k; ++i){int k1=v[i].size(), k2=v[i+1].size();if (k2==1 || v[i][k1-1]<v[i+1][1]){if (k1==1 || v[i+1][0]>v[i][k1-2]) ans++;}}if (ans){cout << k-1 << " " << ans << "\n";return 0;}for (ll i=1; i<=n+1; ++i){while (l[i].size()) l[i].pop_back();while (p[i].size()) p[i].pop_back();h[i][1][1]=0;h[i][1][2]=0;h[i][2][1]=0;h[i][2][2]=0;}for (ll i=1; i<=n; ++i){if (s1[i][1][1]){l[s1[i][1][1]].push_back(i);p[s1[i][1][2]+1].push_back(i);h[i][1][1]=s[i][1][1];h[i][1][2]=s[i][1][2];}if (s1[i][2][1]){l[s1[i][2][1]].push_back(i);p[s1[i][2][2]+1].push_back(i);h[i][2][1]=s[i][2][1];h[i][2][2]=s[i][2][2];}}ans=test();if (ans){cout << k << " " << ans/2 << "\n";return 0;}cout << k+1 << " " << n-1 << "\n";}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 99 |
user output |
---|
2 99 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 100 99 98 97 96 95 94 93 92 91... |
correct output |
---|
98 4851 |
user output |
---|
98 4851 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 88 4 5 6 7 8 9 10 11 12 13... |
correct output |
---|
16 5 |
user output |
---|
16 5 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 51 48 74 70 45 71 24 88 55 99 ... |
correct output |
---|
49 131 |
user output |
---|
49 131 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 45 67 29 62 70 77 41 74 52 95 ... |
correct output |
---|
52 268 |
user output |
---|
52 268 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 47 98 2 75 6 21 84 8 4 89 27 9... |
correct output |
---|
48 149 |
user output |
---|
48 149 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 73 68 17 94 71 63 61 13 58 10 ... |
correct output |
---|
47 116 |
user output |
---|
47 116 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 17 16 45 94 6 1 36 81 31 13 51... |
correct output |
---|
45 95 |
user output |
---|
45 95 |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 4999 |
user output |
---|
2 4999 |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 5000 4999 4998 4997 4996 4995 ... |
correct output |
---|
4998 12492501 |
user output |
---|
4998 12492501 |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
19 10 |
user output |
---|
19 10 |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 264 8 9 10 11 12 1... |
correct output |
---|
190 96 |
user output |
---|
190 96 |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 2400 11 12 1... |
correct output |
---|
1378 27938 |
user output |
---|
1378 27938 |
Test 14
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 4012 2 4820 4208 1868 1728 362... |
correct output |
---|
2511 436307 |
user output |
---|
2511 436307 |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 3877 3972 1112 3669 1959 4640 ... |
correct output |
---|
2497 417065 |
user output |
---|
2497 417065 |
Test 16
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 2774 998 4525 2884 487 1995 41... |
correct output |
---|
2518 426448 |
user output |
---|
2518 426448 |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 199999 |
user output |
---|
2 199999 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
200000 200000 199999 199998 199997 19... |
correct output |
---|
199998 19999700001 |
user output |
---|
199998 19999700001 |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
19 10 |
user output |
---|
19 10 |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
199 100 |
user output |
---|
199 100 |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
1979 1030 |
user output |
---|
1979 1030 |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 184153 4 5 6 7 8 164545 10... |
correct output |
---|
18081 477187 |
user output |
---|
18081 477187 |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
200000 151013 68675 119105 58292 3335... |
correct output |
---|
86328 318722426 |
user output |
---|
86328 318722426 |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
200000 11562 33356 106752 170825 2723... |
correct output |
---|
99873 663048119 |
user output |
---|
99873 663048119 |