Task: | Vaihdot |
Sender: | Laakeri |
Submission time: | 2020-09-04 20:00:07 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 23 |
#3 | ACCEPTED | 64 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 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.01 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.01 s | 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 2, 3 | details |
#12 | ACCEPTED | 0.01 s | 2, 3 | details |
#13 | ACCEPTED | 0.01 s | 2, 3 | details |
#14 | ACCEPTED | 0.01 s | 2, 3 | details |
#15 | ACCEPTED | 0.01 s | 2, 3 | details |
#16 | ACCEPTED | 0.01 s | 2, 3 | details |
#17 | ACCEPTED | 0.15 s | 3 | details |
#18 | ACCEPTED | 0.22 s | 3 | details |
#19 | ACCEPTED | 0.22 s | 3 | details |
#20 | ACCEPTED | 0.22 s | 3 | details |
#21 | ACCEPTED | 0.21 s | 3 | details |
#22 | ACCEPTED | 0.20 s | 3 | details |
#23 | ACCEPTED | 0.30 s | 3 | details |
#24 | ACCEPTED | 0.33 s | 3 | details |
Code
#include <bits/stdc++.h>#define F first#define S second#define X real()#define Y imag();using namespace std;typedef long long ll;typedef long double ld;const int N=1<<18;int st[3][2*N];void add(int j, int i, int v) {for(i+=N;i;i/=2){st[j][i]+=v;}}int sum(int j, int a, int b) {a+=N;b+=N;int s=0;while (a<=b){if (a%2) {s+=st[j][a++];}if (!(b%2)) {s+=st[j][b--];}a/=2;b/=2;}return s;}int a[202020];int pos[202020];int main(){ios_base::sync_with_stdio(0);cin.tie(0);int n;cin>>n;int init=1;for (int i=1;i<=n;i++){cin>>a[i];pos[a[i]]=i;}a[n+1]=n+1;pos[n+1]=n+1;pos[0]=0;a[0]=0;for (int i=1;i<n;i++){if (pos[i+1]<pos[i]){init++;}}vector<tuple<int, int, int, int>> upds;for (int i=1;i<=n;i++){int x=a[i];upds.push_back({i+1, i, 0, 1});int cur=0;vector<int> cps;if (pos[x-1]>i) cps.push_back(pos[x-1]);if (pos[x+1]>i) cps.push_back(pos[x+1]);sort(cps.begin(), cps.end());for (int cp : cps) {upds.push_back({cp, i, cur, -1});if (a[cp]<x){cur++;} else {cur--;}upds.push_back({cp, i, cur, 1});}}sort(upds.begin(), upds.end());int i2=0;vector<ll> ans(5);for (int i=1;i<=n;i++){while (i2<(int)upds.size() && get<0>(upds[i2])==i) {add(get<2>(upds[i2])+1, get<1>(upds[i2]), get<3>(upds[i2]));i2++;}int x=a[i];/*cout<<i<<" "<<x<<endl;for (int j=1;j<=n;j++){int a=sum(0, j, j);int b=sum(1, j, j);int c=sum(2, j, j);assert(a>=0&&b>=0&&c>=0&&a+b+c<=1);if (a+b+c==0){cout<<"xx ";} else {if (a>0){cout<<"-1 ";} else if(b>0){cout<<"00 ";} else {cout<<"+1 ";}}}cout<<endl;*/int cur=0;int p=i-1;vector<int> cps;if (pos[x-1]<i) cps.push_back(pos[x-1]);if (pos[x+1]<i) cps.push_back(pos[x+1]);cps.push_back(0);sort(cps.rbegin(), cps.rend());for (int cp : cps) {for (int j=-1;j<=1;j++){ans[cur+j+2] += (ll)sum(j+1, cp, p);}if (a[cp]>x){cur++;} else {cur--;}p=cp-1;}}for (int i=4;i>=0;i--){if (ans[i]>0){cout<<init-i+2<<" "<<ans[i]<<endl;break;}}}
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 |