CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Vaihdot
Sender:Olli
Submission time:2020-09-06 21:15:56 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED13
#2ACCEPTED23
#3ACCEPTED64
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.02 s2, 3details
#10ACCEPTED0.02 s2, 3details
#11ACCEPTED0.02 s2, 3details
#12ACCEPTED0.02 s2, 3details
#13ACCEPTED0.03 s2, 3details
#14ACCEPTED0.03 s2, 3details
#15ACCEPTED0.03 s2, 3details
#16ACCEPTED0.03 s2, 3details
#17ACCEPTED0.31 s3details
#18ACCEPTED0.27 s3details
#19ACCEPTED0.36 s3details
#20ACCEPTED0.36 s3details
#21ACCEPTED0.38 s3details
#22ACCEPTED0.46 s3details
#23ACCEPTED0.87 s3details
#24ACCEPTED0.94 s3details

Compiler report

input/code.cpp: In function 'll getAm(int, int)':
input/code.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < in[y+C].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~
input/code.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < beg[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~
input/code.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < en[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~
input/code.cpp:103:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(I < in[x+C].size() && in[x+C][I].F == i) {
         ~~^~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int M = 262144;
#define F first
#define S second
typedef long long ll;
int ne[N];
int t[N];
ll am[5];
const int C = 2;
typedef pair<int, int> pii;
vector<pair<int, pii>> in[10];
int n;
int seg[2*M];
vector<int> beg[N];
vector<int> en[N];
int getSum(int a, int b) {
a+=M;
b+=M;
int s = 0;
while(a <= b) {
if(a%2 == 1) {
s += seg[a];
++a;
}
if(b%2 == 0) {
s += seg[b];
--b;
}
a/=2; b/=2;
}
return s;
}
void upd(int i, int x) {
i+=M;
seg[i] += x;
i/=2;
while(i > 0) {
seg[i] = seg[2*i] + seg[2*i + 1];
i/=2;
}
}
ll getAm(int x, int y) {
if(in[x+C].size() == 0 || in[y+C].size() == 0) return 0;
//Get the number of pairs with gains x and y
ll ans = 0;
for(int i = 0; i <= n+2; ++i) {
beg[i].clear();
en[i].clear();
}
for(int i = 0; i < in[y+C].size(); ++i) {
int Y = in[y+C][i].F;
int a = in[y+C][i].S.F;
if(a == -1) a = 0;
int b = in[y+C][i].S.S;
beg[a].push_back(Y);
en[b+1].push_back(Y);
}
for(int i = 1; i < 2*M; ++i) {
seg[i] = 0;
}
int i = 0;
int I = 0;
while(i <= n) {
for(int j = 0; j < beg[i].size(); ++j) {
upd(beg[i][j], 1);
// cout << "Add 1 to " << beg[i][j] << "\n";
}
for(int j = 0; j < en[i].size(); ++j) {
upd(en[i][j], -1);
// cout << "Erase 1 from " << en[i][j] << "\n";
}
while(I < in[x+C].size() && in[x+C][I].F == i) {
// cout << "Here " << i << "\n";
// cout << in[x+C][I].S.F << " " << in[x+C][I].S.S << "\n";
ans += (ll) getSum(in[x+C][I].S.F, in[x+C][I].S.S);
++I;
}
++i;
}
return ans;
}
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> t[i];
// t[i] = n - i + 1;
}
for(int i = 1; i <= n; ++i) {
ne[t[i]] = i;
}
ne[n+1] = n+1;
int inc = 0;
for(int i = 1; i <= n+1; ++i) {
if(ne[i] < ne[i-1]) ++inc;
}
++inc;
// cout << inc << "\n";
/*
Check if one swaps i and i+1
*/
for(int i = 0; i <= n+1; ++i) {
// cout << ne[i] << " ";
}
// cout << "\n";
for(int i = 1; i <= n-1; ++i) {
//Swap i and i+1
if(ne[i-1] < ne[i]) {
if(ne[i+1] < ne[i-1]) {
if(ne[i+2] > ne[i] || ne[i+2] < ne[i+1]) {
++am[0+C];
} else {
++am[-1+C];
}
} else if(ne[i+1] < ne[i]) {
if(ne[i+2] > ne[i+1] && ne[i+2] < ne[i]) {
++am[0+C];
} else {
++am[1+C];
}
} else {
if(ne[i+2] < ne[i+1] && ne[i+2] > ne[i]) {
++am[0+C];
} else {
++am[-1+C];
}
}
} else {
if(ne[i+1] < ne[i]) {
if(ne[i+2] < ne[i+1]) {
++am[1+C];
} else if (ne[i+2] < ne[i]) {
++am[0+C];
} else {
++am[1+C];
}
} else if(ne[i+1] < ne[i-1]) {
if(ne[i+2] > ne[i] && ne[i+2] < ne[i+1]) {
++am[0+C];
} else {
++am[-1+C];
}
} else {
if(ne[i+2] > ne[i] && ne[i+2] < ne[i+1]) {
++am[1+C];
} else {
++am[0+C];
}
}
}
// cout << i << " " << am[0+C] << "\n";
}
// cout << am[-1+C] << "\n";
// cout << am[0+C] << "\n";
// cout << am[1+C] << "\n";
/*
Do interval decomposition
*/
for(int i = 1; i <= n; ++i) {
int a = ne[i-1];
int b = ne[i];
int c = ne[i+1];
if(a < c) {
if(a < b && b < c) {
in[0+C].push_back({b, {a+1, b-1}});
in[0+C].push_back({b, {b+1, c-1}});
in[-1+C].push_back({b, {-1, a-1}});
in[-1+C].push_back({b, {c+1, n+2}});
} else if (b < a) {
in[1+C].push_back({b, {a+1, c-1}});
in[0+C].push_back({b, {-1, b-1}});
in[0+C].push_back({b, {b+1, a-1}});
in[0+C].push_back({b, {c+1, n+2}});
} else {
in[1+C].push_back({b, {a+1, c-1}});
in[0+C].push_back({b, {c+1, b-1}});
in[0+C].push_back({b, {b+1, n+2}});
in[0+C].push_back({b, {-1, a-1}});
}
} else {
if(b > a) {
in[0+C].push_back({b, {-1, c-1}});
in[-1+C].push_back({b, {c+1, a-1}});
in[0+C].push_back({b, {a+1, b-1}});
in[0+C].push_back({b, {b+1, n+2}});
} else if (c < b) {
in[0+C].push_back({b, {c+1, b-1}});
in[0+C].push_back({b, {b+1, a-1}});
in[1+C].push_back({b, {a+1, n+2}});
in[1+C].push_back({b, {-1, c-1}});
} else {
in[0+C].push_back({b, {-1, b-1}});
in[0+C].push_back({b, {b+1, c-1}});
in[-1+C].push_back({b, {c+1, a-1}});
in[0+C].push_back({b, {a+1, n+2}});
}
}
}
for(int i = -1; i <= 1; ++i) {
sort(in[i+C].begin(), in[i+C].end());
}
/*
cout << "\n\n";
for(int i = 0; i <= n+1; ++i) {
cout << ne[i] << " ";
}
cout << "\n";
for(int i = 0; i < in[1+C].size(); ++i) {
cout << in[1+C][i].F << " " << in[1+C][i].S.F << " " << in[1+C][i].S.S << "\n";
}
cout << "\n\n";
for(int i = 0; i < in[0+C].size(); ++i) {
cout << in[0+C][i].F << " " << in[0+C][i].S.F << " " << in[0+C][i].S.S << "\n";
}
cout << getAm(0, 1) << "\n";
return 0;
*/
/*
Check the number of interval pairings
Requires a "sweeping line" technique and a segment tree
(Do this with a function so all pairs can be handled at once)
*/
for(int x = -1; x <= 1; ++x) {
for(int y = x; y <= 1; ++y) {
ll c = 1;
if(x == y) c = 2;
am[x+y+C] += getAm(x, y)/c;
// cout << x << " " << y << " " << getAm(x, y) << "\n";
}
}
for(int i = 2; i >= -2; --i) {
if(am[i+C] > 0) {
cout << inc - i << " " << am[i+C] << "\n";
return 0;
}
}
}

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