Task: | Vaihdot |
Sender: | ollpu |
Submission time: | 2020-09-04 22:11:10 +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.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.02 s | 2, 3 | details |
#12 | ACCEPTED | 0.01 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.34 s | 3 | details |
#18 | ACCEPTED | 0.36 s | 3 | details |
#19 | ACCEPTED | 0.36 s | 3 | details |
#20 | ACCEPTED | 0.37 s | 3 | details |
#21 | ACCEPTED | 0.35 s | 3 | details |
#22 | ACCEPTED | 0.40 s | 3 | details |
#23 | ACCEPTED | 0.71 s | 3 | details |
#24 | ACCEPTED | 0.81 s | 3 | details |
Code
#include <bits/stdc++.h>using namespace std;const int N = 1<<18;int sp[8][2*N];int up[N], wi[N];int p[N];void sp_add(int act, int x, int v) {int k = act << 2 | up[x] << 1 | wi[x];x = p[x];x += N;do {sp[k][x] += v;} while (x /= 2);}int sp_get(int act, int qup, int qwi, int a, int b, int ep) {int k = act << 2 | qup << 1 | qwi;int res = 0;if (a <= ep && ep <= b) res -= sp[k][N+ep];a += N;b += N;while (a <= b) {if (a&1) res += sp[k][a++];if (~b&1) res += sp[k][b--];a /= 2; b /= 2;}return res;}int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;int ord[n];for (int i = 0; i < n; ++i) {cin >> ord[i];ord[i]--;p[ord[i]] = i;}long res = 1e9, resc = 0;auto offer = [&](int v, int c) {if (!c) return;if (v < res) {res = v;resc = c;} else if (v == res) resc += c;};int ires = 0;for (int i = 0; i < n-1; ++i) {ires += p[i+1] < p[i];}for (int i = 0; i < n-1; ++i) {int ores = ires;for (int j = max(i-1, 0); j <= min(i+1, n-2); ++j) {ores -= p[j+1] < p[j];}swap(p[i], p[i+1]);for (int j = max(i-1, 0); j <= min(i+1, n-2); ++j) {ores += p[j+1] < p[j];}swap(p[i], p[i+1]);offer(ores, 2);}int l[n], r[n], cst[n];int lo[n], hi[n];l[0] = -1;r[n-1] = n;vector<int> acbfr[2][n+1];for (int i = 1; i < n; ++i) l[i] = p[i-1];for (int i = 0; i < n-1; ++i) r[i] = p[i+1];for (int i = 0; i < n; ++i) {tie(lo[i], hi[i]) = minmax(l[i], r[i]);acbfr[0][hi[i]].push_back(i);acbfr[1][lo[i]+1].push_back(i);cst[i] = (p[i] < l[i]) + (p[i] > r[i]);up[i] = r[i] > l[i];wi[i] = lo[i] < p[i] && p[i] < hi[i];sp_add(0, i, 1);}for (int t = 0; t < n; ++t) {int i = ord[t];for (int k : {0, 1}) {for (auto x : acbfr[k][t]) {sp_add(!k, x, -1);sp_add(k, x, 1);}}int i2res = ires-cst[i];for (int tup : {0, 1}) {for (int twi : {0, 1}) {int tcst = 1;if (twi) tcst = 2*!tup;int ores = i2res-tcst;offer(ores + 2, sp_get(0, tup, twi, 0, lo[i]-1, p[i]));offer(ores + 1 + 2*!up[i], sp_get(0, tup, twi, lo[i]+1, hi[i]-1, p[i]));offer(ores + 2, sp_get(0, tup, twi, hi[i]+1, N-1, p[i]));offer(ores + 2*!tup + 1, sp_get(1, tup, twi, 0, lo[i]-1, p[i]));offer(ores + 2*!tup + 2*!up[i], sp_get(1, tup, twi, lo[i]+1, hi[i]-1, p[i]));offer(ores + 2*!tup + 1, sp_get(1, tup, twi, hi[i]+1, N-1, p[i]));}}}cout << res+1 << " " << resc/2 << endl;}
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 |