# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
461403 |
2021-08-10T01:20:06 Z |
SHZhang |
Seats (IOI18_seats) |
C++14 |
|
3645 ms |
176704 KB |
#include "seats.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int h, w;
int x[1000005], y[1000005];
int* grid[1000005];
int delta[1000005];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
struct Segtree {
int l, r;
Segtree* lchild;
Segtree* rchild;
int minv, freq, lazy;
};
Segtree* build(int l, int r)
{
Segtree* st = new Segtree;
st->l = l; st->r = r;
st->minv = 0; st->freq = 1; st->lazy = 0;
if (l == r) {
st->lchild = st->rchild = NULL;
} else {
st->lchild = build(l, (l + r) / 2);
st->rchild = build((l + r) / 2 + 1, r);
}
return st;
}
void pushdown(Segtree* st)
{
int val = st->lazy;
st->minv += val;
st->lazy = 0;
if (st->l == st->r) return;
st->lchild->lazy += val;
st->rchild->lazy += val;
}
void modify(Segtree* st, int l, int r, int change)
{
pushdown(st);
if (st->r < l || r < st->l) return;
if (l <= st->l && st->r <= r) {
st->lazy += change;
pushdown(st);
} else {
modify(st->lchild, l, r, change);
modify(st->rchild, l, r, change);
st->minv = min(st->lchild->minv, st->rchild->minv);
if (st->lchild->minv == st->rchild->minv) {
st->freq = st->lchild->freq + st->rchild->freq;
} else if (st->lchild->minv < st->rchild->minv) {
st->freq = st->lchild->freq;
} else {
st->freq = st->rchild->freq;
}
}
}
Segtree* root;
int get_time_weight(int r, int c, int t)
{
//fprintf(stderr, "! %d %d %d\n", r, c, t);
if (grid[r][c] > t) {
int hcnt = 0;
for (int d = 0; d < 4; d++) {
if (r + dx[d] >= 0 && c + dy[d] >= 0 && grid[r + dx[d]][c + dy[d]] <= t) hcnt++;
}
return hcnt >= 2 ? 1 : 0;
} else {
int ccnt = 0;
for (int d = 0; d < 4; d++) {
//printf("! %d %d %d\n", r + dx[d], c + dy[d], (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t));
if (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t) {
int d2 = (d + 1) % 4;
if (r + dx[d2] < 0 || c + dy[d2] < 0 || grid[r + dx[d2]][c + dy[d2]] > t) ccnt++;
}
}
//printf("!! %d\n", lcnt);
return ccnt;
}
}
int get_delta(int r, int c)
{
int diff = get_time_weight(r, c, grid[r][c]) - get_time_weight(r, c, grid[r][c] - 1);
for (int d = 0; d < 4; d++) {
int r2 = r + dx[d];
int c2 = c + dy[d];
if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w) continue;
diff += get_time_weight(r2, c2, grid[r][c]);
diff -= get_time_weight(r2, c2, grid[r][c] - 1);
}
return diff;
}
void update_delta(int r, int c)
{
//fprintf(stderr, "! %d %d\n", r, c);
if (r < 0 || r >= h || c < 0 || c >= w) return;
int id = grid[r][c];
int old_delta = delta[id];
delta[id] = get_delta(r, c);
//fprintf(stderr, "! %d %d\n", r, c);
modify(root, id, h * w - 1, delta[id] - old_delta);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
root = build(0, h * w - 1);
for (int i = 0; i <= h; i++) {
grid[i] = new int[w + 1];
}
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
grid[i][j] = h * w;
}
}
for (int i = 0; i < h * w; i++) {
x[i] = R[i]; y[i] = C[i];
grid[x[i]][y[i]] = i;
//printf("! %d %d %d\n", x[i], y[i], i);
}
//fprintf(stderr, "! %d %d %d\n", grid[0][0], get_time_weight(1, 0, 0), get_time_weight(1, 0, 1));
for (int i = 0; i < h * w; i++) {
update_delta(x[i], y[i]);
//fprintf(stderr, "%d ", delta[i]);
}
//fprintf(stderr, "\n");
}
int swap_seats(int a, int b) {
int x1 = x[a];
int y1 = y[a];
int x2 = x[b];
int y2 = y[b];
swap(grid[x1][y1], grid[x2][y2]);
x[a] = x2; y[a] = y2;
x[b] = x1; y[b] = y1;
for (int d1 = -2; d1 <= 2; d1++) {
for (int d2 = -2; d2 <= 2; d2++) {
if (max(d1, -d1) + max(d2, -d2) > 2) continue;
update_delta(x1 + d1, y1 + d2);
update_delta(x2 + d1, y2 + d2);
}
}
//fprintf(stderr, "! %d %d\n", get_time_weight(1, 1, 1), get_time_weight(1, 1, 2));
/*for (int i = 0; i < h * w; i++) {
fprintf(stderr, "%d ", delta[i]);
}*/
//fprintf(stderr, "\n");
return root->freq;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
444 KB |
Output is correct |
2 |
Correct |
36 ms |
440 KB |
Output is correct |
3 |
Correct |
50 ms |
464 KB |
Output is correct |
4 |
Correct |
16 ms |
456 KB |
Output is correct |
5 |
Correct |
16 ms |
460 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
452 KB |
Output is correct |
8 |
Correct |
41 ms |
436 KB |
Output is correct |
9 |
Correct |
40 ms |
452 KB |
Output is correct |
10 |
Correct |
50 ms |
440 KB |
Output is correct |
11 |
Correct |
30 ms |
456 KB |
Output is correct |
12 |
Correct |
15 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
444 KB |
Output is correct |
2 |
Correct |
36 ms |
440 KB |
Output is correct |
3 |
Correct |
50 ms |
464 KB |
Output is correct |
4 |
Correct |
16 ms |
456 KB |
Output is correct |
5 |
Correct |
16 ms |
460 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
452 KB |
Output is correct |
8 |
Correct |
41 ms |
436 KB |
Output is correct |
9 |
Correct |
40 ms |
452 KB |
Output is correct |
10 |
Correct |
50 ms |
440 KB |
Output is correct |
11 |
Correct |
30 ms |
456 KB |
Output is correct |
12 |
Correct |
15 ms |
460 KB |
Output is correct |
13 |
Correct |
101 ms |
1760 KB |
Output is correct |
14 |
Correct |
98 ms |
1776 KB |
Output is correct |
15 |
Correct |
36 ms |
1812 KB |
Output is correct |
16 |
Correct |
35 ms |
2124 KB |
Output is correct |
17 |
Correct |
64 ms |
1796 KB |
Output is correct |
18 |
Correct |
87 ms |
1892 KB |
Output is correct |
19 |
Correct |
76 ms |
1796 KB |
Output is correct |
20 |
Correct |
56 ms |
1868 KB |
Output is correct |
21 |
Correct |
35 ms |
1816 KB |
Output is correct |
22 |
Correct |
36 ms |
2136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1510 ms |
141492 KB |
Output is correct |
2 |
Correct |
1295 ms |
141640 KB |
Output is correct |
3 |
Correct |
1297 ms |
141564 KB |
Output is correct |
4 |
Correct |
1290 ms |
141528 KB |
Output is correct |
5 |
Correct |
1318 ms |
141484 KB |
Output is correct |
6 |
Correct |
1223 ms |
141564 KB |
Output is correct |
7 |
Correct |
1261 ms |
141616 KB |
Output is correct |
8 |
Correct |
1290 ms |
141544 KB |
Output is correct |
9 |
Correct |
1219 ms |
141556 KB |
Output is correct |
10 |
Correct |
1245 ms |
141584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
1860 KB |
Output is correct |
2 |
Correct |
197 ms |
12884 KB |
Output is correct |
3 |
Correct |
1335 ms |
141572 KB |
Output is correct |
4 |
Correct |
1503 ms |
141700 KB |
Output is correct |
5 |
Correct |
1093 ms |
145456 KB |
Output is correct |
6 |
Correct |
1516 ms |
176704 KB |
Output is correct |
7 |
Correct |
1185 ms |
142904 KB |
Output is correct |
8 |
Correct |
1306 ms |
141504 KB |
Output is correct |
9 |
Correct |
1280 ms |
141728 KB |
Output is correct |
10 |
Correct |
1248 ms |
144576 KB |
Output is correct |
11 |
Correct |
1237 ms |
157188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
1976 KB |
Output is correct |
2 |
Correct |
124 ms |
1920 KB |
Output is correct |
3 |
Correct |
151 ms |
1928 KB |
Output is correct |
4 |
Correct |
204 ms |
2100 KB |
Output is correct |
5 |
Correct |
290 ms |
3300 KB |
Output is correct |
6 |
Correct |
1600 ms |
146464 KB |
Output is correct |
7 |
Correct |
1667 ms |
146336 KB |
Output is correct |
8 |
Correct |
1580 ms |
146376 KB |
Output is correct |
9 |
Correct |
2084 ms |
146468 KB |
Output is correct |
10 |
Correct |
1513 ms |
146324 KB |
Output is correct |
11 |
Correct |
1479 ms |
146408 KB |
Output is correct |
12 |
Correct |
1444 ms |
146308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
444 KB |
Output is correct |
2 |
Correct |
36 ms |
440 KB |
Output is correct |
3 |
Correct |
50 ms |
464 KB |
Output is correct |
4 |
Correct |
16 ms |
456 KB |
Output is correct |
5 |
Correct |
16 ms |
460 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
40 ms |
452 KB |
Output is correct |
8 |
Correct |
41 ms |
436 KB |
Output is correct |
9 |
Correct |
40 ms |
452 KB |
Output is correct |
10 |
Correct |
50 ms |
440 KB |
Output is correct |
11 |
Correct |
30 ms |
456 KB |
Output is correct |
12 |
Correct |
15 ms |
460 KB |
Output is correct |
13 |
Correct |
101 ms |
1760 KB |
Output is correct |
14 |
Correct |
98 ms |
1776 KB |
Output is correct |
15 |
Correct |
36 ms |
1812 KB |
Output is correct |
16 |
Correct |
35 ms |
2124 KB |
Output is correct |
17 |
Correct |
64 ms |
1796 KB |
Output is correct |
18 |
Correct |
87 ms |
1892 KB |
Output is correct |
19 |
Correct |
76 ms |
1796 KB |
Output is correct |
20 |
Correct |
56 ms |
1868 KB |
Output is correct |
21 |
Correct |
35 ms |
1816 KB |
Output is correct |
22 |
Correct |
36 ms |
2136 KB |
Output is correct |
23 |
Correct |
1510 ms |
141492 KB |
Output is correct |
24 |
Correct |
1295 ms |
141640 KB |
Output is correct |
25 |
Correct |
1297 ms |
141564 KB |
Output is correct |
26 |
Correct |
1290 ms |
141528 KB |
Output is correct |
27 |
Correct |
1318 ms |
141484 KB |
Output is correct |
28 |
Correct |
1223 ms |
141564 KB |
Output is correct |
29 |
Correct |
1261 ms |
141616 KB |
Output is correct |
30 |
Correct |
1290 ms |
141544 KB |
Output is correct |
31 |
Correct |
1219 ms |
141556 KB |
Output is correct |
32 |
Correct |
1245 ms |
141584 KB |
Output is correct |
33 |
Correct |
89 ms |
1860 KB |
Output is correct |
34 |
Correct |
197 ms |
12884 KB |
Output is correct |
35 |
Correct |
1335 ms |
141572 KB |
Output is correct |
36 |
Correct |
1503 ms |
141700 KB |
Output is correct |
37 |
Correct |
1093 ms |
145456 KB |
Output is correct |
38 |
Correct |
1516 ms |
176704 KB |
Output is correct |
39 |
Correct |
1185 ms |
142904 KB |
Output is correct |
40 |
Correct |
1306 ms |
141504 KB |
Output is correct |
41 |
Correct |
1280 ms |
141728 KB |
Output is correct |
42 |
Correct |
1248 ms |
144576 KB |
Output is correct |
43 |
Correct |
1237 ms |
157188 KB |
Output is correct |
44 |
Correct |
59 ms |
1976 KB |
Output is correct |
45 |
Correct |
124 ms |
1920 KB |
Output is correct |
46 |
Correct |
151 ms |
1928 KB |
Output is correct |
47 |
Correct |
204 ms |
2100 KB |
Output is correct |
48 |
Correct |
290 ms |
3300 KB |
Output is correct |
49 |
Correct |
1600 ms |
146464 KB |
Output is correct |
50 |
Correct |
1667 ms |
146336 KB |
Output is correct |
51 |
Correct |
1580 ms |
146376 KB |
Output is correct |
52 |
Correct |
2084 ms |
146468 KB |
Output is correct |
53 |
Correct |
1513 ms |
146324 KB |
Output is correct |
54 |
Correct |
1479 ms |
146408 KB |
Output is correct |
55 |
Correct |
1444 ms |
146308 KB |
Output is correct |
56 |
Correct |
218 ms |
2124 KB |
Output is correct |
57 |
Correct |
489 ms |
2072 KB |
Output is correct |
58 |
Correct |
777 ms |
3356 KB |
Output is correct |
59 |
Correct |
2787 ms |
142564 KB |
Output is correct |
60 |
Correct |
3645 ms |
142528 KB |
Output is correct |
61 |
Correct |
2322 ms |
142496 KB |
Output is correct |
62 |
Correct |
1774 ms |
144452 KB |
Output is correct |
63 |
Correct |
2975 ms |
143880 KB |
Output is correct |
64 |
Correct |
2563 ms |
142928 KB |
Output is correct |
65 |
Correct |
2352 ms |
142588 KB |
Output is correct |
66 |
Correct |
2761 ms |
142644 KB |
Output is correct |
67 |
Correct |
2400 ms |
145556 KB |
Output is correct |
68 |
Correct |
1921 ms |
151596 KB |
Output is correct |
69 |
Correct |
2792 ms |
158280 KB |
Output is correct |