# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
492211 |
2021-12-06T00:34:48 Z |
peti1234 |
Seats (IOI18_seats) |
C++17 |
|
3342 ms |
85424 KB |
#include <bits/stdc++.h>
using namespace std;
const int c=1000002, p=1048576;
int n, m, k, sor[c], pos[c], oszlop[c], kezd[2*p], veg[2*p], kert[2*p], kdb[2*p], lp[2*p], t[4];
bool jo[c];
int st, fi, ert;
void add(int a) {
int k=kezd[a], v=veg[a], x=2*a, y=2*a+1;
if (st>v || fi<k) return;
if (st<=k && v<=fi) lp[a]+=ert;
else {
add(x), add(y);
int p=kert[x]+lp[x], q=kert[y]+lp[y];
kert[a]=min(p, q);
kdb[a]=0;
if (kert[a]==p) kdb[a]+=kdb[x];
if (kert[a]==q) kdb[a]+=kdb[y];
}
}
int ki(int a, int b) {
if (a<0 || a>=n || b<0 || b>=m) return k;
return pos[a*m+b];
}
void upd(int a, int b, int c) {
t[0]=ki(a-1, b-1), t[1]=ki(a-1, b), t[2]=ki(a, b-1), t[3]=ki(a, b);
sort(t, t+4);
ert=c;
if (t[0]!=t[1]) st=t[0], fi=t[1]-1, add(1);
if (t[2]!=t[3]) st=t[2], fi=t[3]-1, add(1);
}
void kupd(int a, int b, int c) {
upd(a+1, b+1, c), upd(a+1, b, c);
upd(a, b+1, c), upd(a, b, c);
}
int swap_seats(int a, int b) {
kupd(sor[a], oszlop[a], -1), kupd(sor[b], oszlop[b], -1);
swap(sor[a], sor[b]), swap(oszlop[a], oszlop[b]);
pos[sor[a]*m+oszlop[a]]=a, pos[sor[b]*m+oszlop[b]]=b;
kupd(sor[a], oszlop[a], 1), kupd(sor[b], oszlop[b], 1);
return kdb[1];
}
void give_initial_chart(int a, int b, vector<int> c, vector<int> d) {
n=a, m=b, k=n*m;
for (int i=0; i<k; i++) sor[i]=c[i], oszlop[i]=d[i], pos[sor[i]*m+oszlop[i]]=i;
for (int i=p; i<2*p; i++) {
int x=i-p;
kezd[i]=x, veg[i]=x, kdb[i]=1;
if (x<k) kert[i]=0;
else kert[i]=p;
}
for (int i=p-1; i>=0; i--) {
int x=2*i, y=2*i+1;
kezd[i]=kezd[x], veg[i]=veg[y];
kert[i]=min(kert[x], kert[y]);
if (kert[x]==kert[i]) kdb[i]+=kdb[x];
if (kert[y]==kert[i]) kdb[i]+=kdb[y];
}
for (int i=0; i<=n; i++) for (int j=0; j<=m; j++) upd(i, j, 1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
33328 KB |
Output is correct |
2 |
Correct |
105 ms |
33416 KB |
Output is correct |
3 |
Correct |
115 ms |
33420 KB |
Output is correct |
4 |
Correct |
74 ms |
33304 KB |
Output is correct |
5 |
Correct |
70 ms |
33328 KB |
Output is correct |
6 |
Correct |
95 ms |
33288 KB |
Output is correct |
7 |
Correct |
104 ms |
33292 KB |
Output is correct |
8 |
Correct |
111 ms |
33348 KB |
Output is correct |
9 |
Correct |
104 ms |
33348 KB |
Output is correct |
10 |
Correct |
103 ms |
33348 KB |
Output is correct |
11 |
Correct |
98 ms |
33296 KB |
Output is correct |
12 |
Correct |
69 ms |
33348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
33328 KB |
Output is correct |
2 |
Correct |
105 ms |
33416 KB |
Output is correct |
3 |
Correct |
115 ms |
33420 KB |
Output is correct |
4 |
Correct |
74 ms |
33304 KB |
Output is correct |
5 |
Correct |
70 ms |
33328 KB |
Output is correct |
6 |
Correct |
95 ms |
33288 KB |
Output is correct |
7 |
Correct |
104 ms |
33292 KB |
Output is correct |
8 |
Correct |
111 ms |
33348 KB |
Output is correct |
9 |
Correct |
104 ms |
33348 KB |
Output is correct |
10 |
Correct |
103 ms |
33348 KB |
Output is correct |
11 |
Correct |
98 ms |
33296 KB |
Output is correct |
12 |
Correct |
69 ms |
33348 KB |
Output is correct |
13 |
Correct |
103 ms |
33760 KB |
Output is correct |
14 |
Correct |
122 ms |
33760 KB |
Output is correct |
15 |
Correct |
75 ms |
33740 KB |
Output is correct |
16 |
Correct |
56 ms |
33732 KB |
Output is correct |
17 |
Correct |
88 ms |
33772 KB |
Output is correct |
18 |
Correct |
84 ms |
33760 KB |
Output is correct |
19 |
Correct |
85 ms |
33756 KB |
Output is correct |
20 |
Correct |
69 ms |
33868 KB |
Output is correct |
21 |
Correct |
58 ms |
33760 KB |
Output is correct |
22 |
Correct |
56 ms |
33764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2215 ms |
68980 KB |
Output is correct |
2 |
Correct |
998 ms |
69000 KB |
Output is correct |
3 |
Correct |
990 ms |
69044 KB |
Output is correct |
4 |
Correct |
772 ms |
69044 KB |
Output is correct |
5 |
Correct |
836 ms |
68956 KB |
Output is correct |
6 |
Correct |
802 ms |
69052 KB |
Output is correct |
7 |
Correct |
904 ms |
68928 KB |
Output is correct |
8 |
Correct |
1006 ms |
68992 KB |
Output is correct |
9 |
Correct |
929 ms |
69056 KB |
Output is correct |
10 |
Correct |
900 ms |
68868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
33780 KB |
Output is correct |
2 |
Correct |
173 ms |
36872 KB |
Output is correct |
3 |
Correct |
822 ms |
68916 KB |
Output is correct |
4 |
Correct |
2175 ms |
68936 KB |
Output is correct |
5 |
Correct |
744 ms |
65132 KB |
Output is correct |
6 |
Correct |
1783 ms |
68932 KB |
Output is correct |
7 |
Correct |
795 ms |
67912 KB |
Output is correct |
8 |
Correct |
1002 ms |
68924 KB |
Output is correct |
9 |
Correct |
1065 ms |
66524 KB |
Output is correct |
10 |
Correct |
866 ms |
68760 KB |
Output is correct |
11 |
Correct |
739 ms |
67900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
539 ms |
34648 KB |
Output is correct |
2 |
Correct |
556 ms |
34700 KB |
Output is correct |
3 |
Correct |
524 ms |
34580 KB |
Output is correct |
4 |
Correct |
410 ms |
34600 KB |
Output is correct |
5 |
Correct |
456 ms |
34940 KB |
Output is correct |
6 |
Correct |
1145 ms |
66756 KB |
Output is correct |
7 |
Correct |
1406 ms |
68792 KB |
Output is correct |
8 |
Correct |
1124 ms |
64876 KB |
Output is correct |
9 |
Correct |
2594 ms |
68812 KB |
Output is correct |
10 |
Correct |
1087 ms |
66752 KB |
Output is correct |
11 |
Correct |
1072 ms |
67900 KB |
Output is correct |
12 |
Correct |
1044 ms |
64984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
33328 KB |
Output is correct |
2 |
Correct |
105 ms |
33416 KB |
Output is correct |
3 |
Correct |
115 ms |
33420 KB |
Output is correct |
4 |
Correct |
74 ms |
33304 KB |
Output is correct |
5 |
Correct |
70 ms |
33328 KB |
Output is correct |
6 |
Correct |
95 ms |
33288 KB |
Output is correct |
7 |
Correct |
104 ms |
33292 KB |
Output is correct |
8 |
Correct |
111 ms |
33348 KB |
Output is correct |
9 |
Correct |
104 ms |
33348 KB |
Output is correct |
10 |
Correct |
103 ms |
33348 KB |
Output is correct |
11 |
Correct |
98 ms |
33296 KB |
Output is correct |
12 |
Correct |
69 ms |
33348 KB |
Output is correct |
13 |
Correct |
103 ms |
33760 KB |
Output is correct |
14 |
Correct |
122 ms |
33760 KB |
Output is correct |
15 |
Correct |
75 ms |
33740 KB |
Output is correct |
16 |
Correct |
56 ms |
33732 KB |
Output is correct |
17 |
Correct |
88 ms |
33772 KB |
Output is correct |
18 |
Correct |
84 ms |
33760 KB |
Output is correct |
19 |
Correct |
85 ms |
33756 KB |
Output is correct |
20 |
Correct |
69 ms |
33868 KB |
Output is correct |
21 |
Correct |
58 ms |
33760 KB |
Output is correct |
22 |
Correct |
56 ms |
33764 KB |
Output is correct |
23 |
Correct |
2215 ms |
68980 KB |
Output is correct |
24 |
Correct |
998 ms |
69000 KB |
Output is correct |
25 |
Correct |
990 ms |
69044 KB |
Output is correct |
26 |
Correct |
772 ms |
69044 KB |
Output is correct |
27 |
Correct |
836 ms |
68956 KB |
Output is correct |
28 |
Correct |
802 ms |
69052 KB |
Output is correct |
29 |
Correct |
904 ms |
68928 KB |
Output is correct |
30 |
Correct |
1006 ms |
68992 KB |
Output is correct |
31 |
Correct |
929 ms |
69056 KB |
Output is correct |
32 |
Correct |
900 ms |
68868 KB |
Output is correct |
33 |
Correct |
113 ms |
33780 KB |
Output is correct |
34 |
Correct |
173 ms |
36872 KB |
Output is correct |
35 |
Correct |
822 ms |
68916 KB |
Output is correct |
36 |
Correct |
2175 ms |
68936 KB |
Output is correct |
37 |
Correct |
744 ms |
65132 KB |
Output is correct |
38 |
Correct |
1783 ms |
68932 KB |
Output is correct |
39 |
Correct |
795 ms |
67912 KB |
Output is correct |
40 |
Correct |
1002 ms |
68924 KB |
Output is correct |
41 |
Correct |
1065 ms |
66524 KB |
Output is correct |
42 |
Correct |
866 ms |
68760 KB |
Output is correct |
43 |
Correct |
739 ms |
67900 KB |
Output is correct |
44 |
Correct |
539 ms |
34648 KB |
Output is correct |
45 |
Correct |
556 ms |
34700 KB |
Output is correct |
46 |
Correct |
524 ms |
34580 KB |
Output is correct |
47 |
Correct |
410 ms |
34600 KB |
Output is correct |
48 |
Correct |
456 ms |
34940 KB |
Output is correct |
49 |
Correct |
1145 ms |
66756 KB |
Output is correct |
50 |
Correct |
1406 ms |
68792 KB |
Output is correct |
51 |
Correct |
1124 ms |
64876 KB |
Output is correct |
52 |
Correct |
2594 ms |
68812 KB |
Output is correct |
53 |
Correct |
1087 ms |
66752 KB |
Output is correct |
54 |
Correct |
1072 ms |
67900 KB |
Output is correct |
55 |
Correct |
1044 ms |
64984 KB |
Output is correct |
56 |
Correct |
783 ms |
34424 KB |
Output is correct |
57 |
Correct |
955 ms |
34412 KB |
Output is correct |
58 |
Correct |
635 ms |
34920 KB |
Output is correct |
59 |
Correct |
1708 ms |
68872 KB |
Output is correct |
60 |
Correct |
3342 ms |
68788 KB |
Output is correct |
61 |
Correct |
1497 ms |
85424 KB |
Output is correct |
62 |
Correct |
1245 ms |
81604 KB |
Output is correct |
63 |
Correct |
3060 ms |
85380 KB |
Output is correct |
64 |
Correct |
1821 ms |
85408 KB |
Output is correct |
65 |
Correct |
1647 ms |
85300 KB |
Output is correct |
66 |
Correct |
1862 ms |
82652 KB |
Output is correct |
67 |
Correct |
1725 ms |
85316 KB |
Output is correct |
68 |
Correct |
1263 ms |
85004 KB |
Output is correct |
69 |
Correct |
2682 ms |
85380 KB |
Output is correct |