# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
75083 |
2018-09-08T09:30:57 Z |
ics0503 |
Seats (IOI18_seats) |
C++17 |
|
3171 ms |
153344 KB |
#include "seats.h"
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int h, w, n;
struct ND {int am, as, bm, bs, S, alaz,blaz;}tree[4141414];
int min(int a, int b) { if (a < b)return a; return b; }
int max(int a, int b) { if (a > b)return a; return b; }
void update(int w) {
int c1 = w << 1, c2 = (w << 1) + 1;
tree[w].am = min(tree[c1].am, tree[c2].am);
tree[w].bm = min(tree[c1].bm, tree[c2].bm);
tree[w].as = tree[w].bs = tree[w].S = 0;
if (tree[w].am == tree[c1].am)tree[w].as += tree[c1].as;
if (tree[w].am == tree[c2].am)tree[w].as += tree[c2].as;
if (tree[w].bm == tree[c1].bm)tree[w].bs += tree[c1].bs;
if (tree[w].bm == tree[c2].bm)tree[w].bs += tree[c2].bs;
if (tree[w].am == tree[c1].am && tree[w].bm == tree[c1].bm)tree[w].S += tree[c1].S;
if (tree[w].am == tree[c2].am && tree[w].bm == tree[c2].bm)tree[w].S += tree[c2].S;
}
void lazy(int w) {
if (tree[w].alaz == 0 && tree[w].blaz == 0)return;
int c1 = w << 1, c2 = (w << 1) + 1;
tree[c1].alaz += tree[w].alaz, tree[c2].alaz += tree[w].alaz;
tree[c1].blaz += tree[w].blaz, tree[c2].blaz += tree[w].blaz;
tree[c1].am += tree[w].alaz; tree[c2].am += tree[w].alaz;
tree[c1].bm += tree[w].blaz; tree[c2].bm += tree[w].blaz;
tree[w].alaz = tree[w].blaz = 0;
}
void insert_g(int w, int s, int e, int l, int r, int tp, int g) {
if (s != e)lazy(w);
if (s == l&&e == r) {
if (tp == 0) {
tree[w].alaz += g;
tree[w].am += g;
}
else{
tree[w].blaz += g;
tree[w].bm += g;
}
return;
}
int m = (s + e) / 2;
if (l <= m)insert_g(w * 2, s, m, l, min(m, r), tp, g);
if (m + 1 <= r)insert_g(w * 2 + 1, m + 1, e, max(m + 1, l), r, tp, g);
update(w);
}
int x[1212121], y[1212121];
vector<int>M[1212121];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int A[1212121], B[1212121];
void init(int w, int s, int e) {
if (s == e) { tree[w].am = A[s], tree[w].bm = B[s], tree[w].S = tree[w].as = tree[w].bs = 1; return; }
int m = (s + e) / 2;
init(w * 2, s, m);
init(w * 2 + 1, m + 1, e);
update(w);
}
int AT[1212121], BT[1212121];
void go_1(int x, int y, int g, int tp = 0) {
int i;
for (i = 0; i < 4; i++) {
int ni = (i + 1) % 4;
int nx = x + dx[i], ny = y + dy[i];
int nnx = x + dx[ni], nny = y + dy[ni];
int si, ei;
si = M[x][y], ei = min(M[nx][ny], M[nnx][nny]) - 1;
if (si <= ei) {
if (tp == 0)insert_g(1, 1, n, si, ei, 0, g);
else AT[si] += g, AT[ei + 1] -= g;
}
si = max(M[nx][ny], M[nnx][nny]), ei = M[x][y] - 1;
if (si <= ei) {
if(tp==0)insert_g(1, 1, n, si, ei, 1, g);
else BT[si] += g, BT[ei + 1] -= g;
}
}
}
void go_2(int x, int y,int rx,int ry, int g) {
int i;
for (i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx == rx&&ny == ry)continue;
int ni, nnx, nny, si, ei;
ni = (i + 1) % 4;
nnx = nx + dx[ni], nny = ny + dy[ni];
si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1;
if (si <= ei)insert_g(1, 1, n, si, ei, 0, g);
si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1;
if (si <= ei)insert_g(1, 1, n, si, ei, 1, g);
ni = (i + 3) % 4;
nnx = nx + dx[ni], nny = ny + dy[ni];
si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1;
if (si <= ei)insert_g(1, 1, n, si, ei, 0, g);
si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1;
if (si <= ei)insert_g(1, 1, n, si, ei, 1, g);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
int i, j;
h = H, w = W; n = H*W;
for (i = 0; i <= h + 1; i++) for (j = 0; j <= w + 1; j++)M[i].push_back(n + 1);
for (i = 0; i < n; i++)x[i + 1] = R[i] + 1, y[i + 1] = C[i] + 1;
for (i = 1; i <= n; i++) M[x[i]][y[i]] = i;
for (i = 1; i <= h; i++) for (j = 1; j <= w; j++) go_1(i, j, 1, 1);
for (i = 1; i <= n; i++)A[i] = A[i - 1] + AT[i], B[i] = B[i - 1] + BT[i];
init(1, 1, n);
}
void swap(int &a, int &b) { int c = a; a = b; b = c; }
int swap_seats(int a, int b) {
a++, b++;
go_1(x[a], y[a], -1); go_2(x[a], y[a], x[b], y[b], -1);
go_1(x[b], y[b], -1); go_2(x[b], y[b], x[a], y[a], -1);
swap(x[a], x[b]), swap(y[a], y[b]);
swap(M[x[a]][y[a]], M[x[b]][y[b]]);
go_1(x[a], y[a], 1); go_2(x[a], y[a], x[b], y[b], 1);
go_1(x[b], y[b], 1); go_2(x[b], y[b], x[a], y[a], 1);
return tree[1].S;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
29052 KB |
Output is correct |
2 |
Correct |
59 ms |
29064 KB |
Output is correct |
3 |
Correct |
85 ms |
29064 KB |
Output is correct |
4 |
Correct |
63 ms |
29064 KB |
Output is correct |
5 |
Correct |
51 ms |
29120 KB |
Output is correct |
6 |
Correct |
77 ms |
29128 KB |
Output is correct |
7 |
Correct |
84 ms |
29248 KB |
Output is correct |
8 |
Correct |
72 ms |
29548 KB |
Output is correct |
9 |
Correct |
70 ms |
29548 KB |
Output is correct |
10 |
Correct |
103 ms |
29548 KB |
Output is correct |
11 |
Correct |
77 ms |
29548 KB |
Output is correct |
12 |
Correct |
52 ms |
29548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
29052 KB |
Output is correct |
2 |
Correct |
59 ms |
29064 KB |
Output is correct |
3 |
Correct |
85 ms |
29064 KB |
Output is correct |
4 |
Correct |
63 ms |
29064 KB |
Output is correct |
5 |
Correct |
51 ms |
29120 KB |
Output is correct |
6 |
Correct |
77 ms |
29128 KB |
Output is correct |
7 |
Correct |
84 ms |
29248 KB |
Output is correct |
8 |
Correct |
72 ms |
29548 KB |
Output is correct |
9 |
Correct |
70 ms |
29548 KB |
Output is correct |
10 |
Correct |
103 ms |
29548 KB |
Output is correct |
11 |
Correct |
77 ms |
29548 KB |
Output is correct |
12 |
Correct |
52 ms |
29548 KB |
Output is correct |
13 |
Correct |
161 ms |
30528 KB |
Output is correct |
14 |
Correct |
178 ms |
30576 KB |
Output is correct |
15 |
Correct |
105 ms |
30676 KB |
Output is correct |
16 |
Correct |
81 ms |
30792 KB |
Output is correct |
17 |
Correct |
126 ms |
30792 KB |
Output is correct |
18 |
Correct |
111 ms |
30792 KB |
Output is correct |
19 |
Correct |
123 ms |
30792 KB |
Output is correct |
20 |
Correct |
99 ms |
30792 KB |
Output is correct |
21 |
Correct |
79 ms |
30792 KB |
Output is correct |
22 |
Correct |
82 ms |
30792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
794 ms |
129856 KB |
Output is correct |
2 |
Correct |
629 ms |
129928 KB |
Output is correct |
3 |
Correct |
620 ms |
129928 KB |
Output is correct |
4 |
Correct |
598 ms |
129928 KB |
Output is correct |
5 |
Correct |
660 ms |
129928 KB |
Output is correct |
6 |
Correct |
618 ms |
129928 KB |
Output is correct |
7 |
Correct |
619 ms |
129928 KB |
Output is correct |
8 |
Correct |
657 ms |
129928 KB |
Output is correct |
9 |
Correct |
798 ms |
129928 KB |
Output is correct |
10 |
Correct |
610 ms |
129988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
129988 KB |
Output is correct |
2 |
Correct |
194 ms |
129988 KB |
Output is correct |
3 |
Correct |
565 ms |
129988 KB |
Output is correct |
4 |
Correct |
803 ms |
129988 KB |
Output is correct |
5 |
Correct |
543 ms |
133912 KB |
Output is correct |
6 |
Correct |
971 ms |
153344 KB |
Output is correct |
7 |
Correct |
564 ms |
153344 KB |
Output is correct |
8 |
Correct |
620 ms |
153344 KB |
Output is correct |
9 |
Correct |
568 ms |
153344 KB |
Output is correct |
10 |
Correct |
610 ms |
153344 KB |
Output is correct |
11 |
Correct |
658 ms |
153344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
153344 KB |
Output is correct |
2 |
Correct |
177 ms |
153344 KB |
Output is correct |
3 |
Correct |
274 ms |
153344 KB |
Output is correct |
4 |
Correct |
379 ms |
153344 KB |
Output is correct |
5 |
Correct |
664 ms |
153344 KB |
Output is correct |
6 |
Correct |
1323 ms |
153344 KB |
Output is correct |
7 |
Correct |
1385 ms |
153344 KB |
Output is correct |
8 |
Correct |
1319 ms |
153344 KB |
Output is correct |
9 |
Correct |
1746 ms |
153344 KB |
Output is correct |
10 |
Correct |
1265 ms |
153344 KB |
Output is correct |
11 |
Correct |
1253 ms |
153344 KB |
Output is correct |
12 |
Correct |
1231 ms |
153344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
29052 KB |
Output is correct |
2 |
Correct |
59 ms |
29064 KB |
Output is correct |
3 |
Correct |
85 ms |
29064 KB |
Output is correct |
4 |
Correct |
63 ms |
29064 KB |
Output is correct |
5 |
Correct |
51 ms |
29120 KB |
Output is correct |
6 |
Correct |
77 ms |
29128 KB |
Output is correct |
7 |
Correct |
84 ms |
29248 KB |
Output is correct |
8 |
Correct |
72 ms |
29548 KB |
Output is correct |
9 |
Correct |
70 ms |
29548 KB |
Output is correct |
10 |
Correct |
103 ms |
29548 KB |
Output is correct |
11 |
Correct |
77 ms |
29548 KB |
Output is correct |
12 |
Correct |
52 ms |
29548 KB |
Output is correct |
13 |
Correct |
161 ms |
30528 KB |
Output is correct |
14 |
Correct |
178 ms |
30576 KB |
Output is correct |
15 |
Correct |
105 ms |
30676 KB |
Output is correct |
16 |
Correct |
81 ms |
30792 KB |
Output is correct |
17 |
Correct |
126 ms |
30792 KB |
Output is correct |
18 |
Correct |
111 ms |
30792 KB |
Output is correct |
19 |
Correct |
123 ms |
30792 KB |
Output is correct |
20 |
Correct |
99 ms |
30792 KB |
Output is correct |
21 |
Correct |
79 ms |
30792 KB |
Output is correct |
22 |
Correct |
82 ms |
30792 KB |
Output is correct |
23 |
Correct |
794 ms |
129856 KB |
Output is correct |
24 |
Correct |
629 ms |
129928 KB |
Output is correct |
25 |
Correct |
620 ms |
129928 KB |
Output is correct |
26 |
Correct |
598 ms |
129928 KB |
Output is correct |
27 |
Correct |
660 ms |
129928 KB |
Output is correct |
28 |
Correct |
618 ms |
129928 KB |
Output is correct |
29 |
Correct |
619 ms |
129928 KB |
Output is correct |
30 |
Correct |
657 ms |
129928 KB |
Output is correct |
31 |
Correct |
798 ms |
129928 KB |
Output is correct |
32 |
Correct |
610 ms |
129988 KB |
Output is correct |
33 |
Correct |
150 ms |
129988 KB |
Output is correct |
34 |
Correct |
194 ms |
129988 KB |
Output is correct |
35 |
Correct |
565 ms |
129988 KB |
Output is correct |
36 |
Correct |
803 ms |
129988 KB |
Output is correct |
37 |
Correct |
543 ms |
133912 KB |
Output is correct |
38 |
Correct |
971 ms |
153344 KB |
Output is correct |
39 |
Correct |
564 ms |
153344 KB |
Output is correct |
40 |
Correct |
620 ms |
153344 KB |
Output is correct |
41 |
Correct |
568 ms |
153344 KB |
Output is correct |
42 |
Correct |
610 ms |
153344 KB |
Output is correct |
43 |
Correct |
658 ms |
153344 KB |
Output is correct |
44 |
Correct |
85 ms |
153344 KB |
Output is correct |
45 |
Correct |
177 ms |
153344 KB |
Output is correct |
46 |
Correct |
274 ms |
153344 KB |
Output is correct |
47 |
Correct |
379 ms |
153344 KB |
Output is correct |
48 |
Correct |
664 ms |
153344 KB |
Output is correct |
49 |
Correct |
1323 ms |
153344 KB |
Output is correct |
50 |
Correct |
1385 ms |
153344 KB |
Output is correct |
51 |
Correct |
1319 ms |
153344 KB |
Output is correct |
52 |
Correct |
1746 ms |
153344 KB |
Output is correct |
53 |
Correct |
1265 ms |
153344 KB |
Output is correct |
54 |
Correct |
1253 ms |
153344 KB |
Output is correct |
55 |
Correct |
1231 ms |
153344 KB |
Output is correct |
56 |
Correct |
232 ms |
153344 KB |
Output is correct |
57 |
Correct |
626 ms |
153344 KB |
Output is correct |
58 |
Correct |
893 ms |
153344 KB |
Output is correct |
59 |
Correct |
2115 ms |
153344 KB |
Output is correct |
60 |
Correct |
3171 ms |
153344 KB |
Output is correct |
61 |
Correct |
1748 ms |
153344 KB |
Output is correct |
62 |
Correct |
1605 ms |
153344 KB |
Output is correct |
63 |
Correct |
2710 ms |
153344 KB |
Output is correct |
64 |
Correct |
1952 ms |
153344 KB |
Output is correct |
65 |
Correct |
1753 ms |
153344 KB |
Output is correct |
66 |
Correct |
2148 ms |
153344 KB |
Output is correct |
67 |
Correct |
1986 ms |
153344 KB |
Output is correct |
68 |
Correct |
1670 ms |
153344 KB |
Output is correct |
69 |
Correct |
2695 ms |
153344 KB |
Output is correct |