# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
195700 |
2020-01-16T22:49:40 Z |
Anai |
Seats (IOI18_seats) |
C++14 |
|
3712 ms |
100984 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifndef HOME
#include "seats.h"
#endif
#define x first
#define y second
using namespace std;
namespace {
using pii = pair<int, int>;
const int A = 1e6 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct Nod {
int min, cnt, lazy;
};
int f[A];
vector<vector<int>> mx;
vector<int> row, col;
int n, m, a;
int ql, qr, qval;
Nod pom[A * 4];
static void prop(int nod) {
pom[2 * nod + 1].lazy+= pom[nod].lazy;
pom[2 * nod].lazy+= pom[nod].lazy;
pom[nod].min+= pom[nod].lazy;
pom[nod].lazy = 0;
}
static void update(int nod, int st, int dr) {
if (qr < ql)
return;
if (ql <= st && dr <= qr) {
pom[nod].lazy+= qval;
return;
}
int mid = (st + dr) / 2;
if (ql <= mid)
update(2 * nod, st, mid);
if (mid < qr)
update(2 * nod + 1, mid + 1, dr);
pom[nod].min = min(pom[2 * nod].min + pom[2 * nod].lazy, pom[2 * nod + 1].min + pom[2 * nod + 1].lazy);
pom[nod].cnt = (pom[nod].min == pom[2 * nod].min + pom[2 * nod].lazy ? pom[2 * nod].cnt : 0);
pom[nod].cnt+= (pom[nod].min == pom[2 * nod + 1].min + pom[2 * nod + 1].lazy ? pom[2 * nod + 1].cnt : 0);
}
static pii query(int nod, int st, int dr) {
if (ql <= st && dr <= qr)
return pii(pom[nod].min + pom[nod].lazy, pom[nod].cnt);
int mid = (st + dr) / 2;
pii ans = {1e9, 1e9};
prop(nod);
if (ql <= mid)
ans = query(2 * nod, st, mid);
if (mid < qr) {
pii ret = query(2 * nod + 1, mid + 1, dr);
if (ret.x < ans.x)
ans = ret;
else if (ret.x == ans.x)
ans.y+= ret.y;
}
return ans;
}
static void act(int idx, int qt = 1) {
static vector<pii> nidx;
nidx.clear();
int x = row[idx], y = col[idx];
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
int val = mx[nx][ny];
nidx.emplace_back(val, dir);
}
sort(begin(nidx), end(nidx));
if (nidx[1].x < idx) {
ql = nidx[1].x;
qr = idx - 1;
qval = 100 * qt;
update(1, 0, a);
}
ql = idx;
qr = nidx[0].x - 1;
qval = 10 * qt;
update(1, 0, a);
ql = max(idx, nidx[0].x);
qr = nidx[1].x - 1;
qval = 2 * qt;
update(1, 0, a);
if (nidx[0].y % 2 == nidx[1].y % 2)
return;
ql = max(idx, nidx[1].x);
qr = nidx[2].x - 1;
qval = qt;
update(1, 0, a);
}
static void baga(int idx) {
if (idx == a || f[idx])
return;
f[idx]++;
act(idx, 1);
}
static void scoate(int idx) {
if (idx == a || f[idx] == 0)
return;
f[idx]--;
act(idx, -1);
}
static void meh(int nod, int st, int dr) {
if (st == dr) {
pom[nod].cnt = 1;
return;
}
int mid = (st + dr) / 2;
meh(2 * nod, st, mid);
meh(2 * nod + 1, mid + 1, dr);
pom[nod].cnt = dr - st + 1;
}
};
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
swap(row, R);
swap(col, C);
n = H;
m = W;
a = n * m;
mx = vector<vector<int>>(n + 5, vector<int>(m + 5));
for (int i = 0; i < a; ++i)
mx[++row[i]][++col[i]] = i;
for (int i = 0; i <= n + 1; ++i)
mx[i][0] = mx[i][m + 1] = a;
for (int j = 0; j <= m + 1; ++j)
mx[0][j] = mx[n + 1][j] = a;
meh(1, 0, a);
ql = qr = 0;
qval = 1000;
update(1, 0, a);
ql = qr = a;
qval = 1000;
update(1, 0, a);
for (int i = 0; i < a; ++i)
baga(i);
}
int swap_seats(int u, int v) {
static int call = 0; ++call;
int xu = row[u], yu = col[u];
int xv = row[v], yv = col[v];
scoate(u);
scoate(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
scoate(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
scoate(mx[nx][ny]);
}
swap(mx[xu][yu], mx[xv][yv]);
swap(col[u], col[v]);
swap(row[u], row[v]);
baga(u);
baga(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
baga(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
baga(mx[nx][ny]);
}
ql = 0, qr = a;
return 1 + pom[1].cnt;
}
#ifdef HOME
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
}; // namespace
int main() {
freopen("seats.in", "r", stdin);
freopen("seats.out", "w", stdout);
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
632 KB |
Output is correct |
2 |
Correct |
26 ms |
504 KB |
Output is correct |
3 |
Correct |
41 ms |
376 KB |
Output is correct |
4 |
Correct |
23 ms |
504 KB |
Output is correct |
5 |
Correct |
18 ms |
504 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
38 ms |
504 KB |
Output is correct |
8 |
Correct |
31 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
31 ms |
632 KB |
Output is correct |
11 |
Correct |
34 ms |
632 KB |
Output is correct |
12 |
Correct |
18 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
632 KB |
Output is correct |
2 |
Correct |
26 ms |
504 KB |
Output is correct |
3 |
Correct |
41 ms |
376 KB |
Output is correct |
4 |
Correct |
23 ms |
504 KB |
Output is correct |
5 |
Correct |
18 ms |
504 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
38 ms |
504 KB |
Output is correct |
8 |
Correct |
31 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
31 ms |
632 KB |
Output is correct |
11 |
Correct |
34 ms |
632 KB |
Output is correct |
12 |
Correct |
18 ms |
504 KB |
Output is correct |
13 |
Correct |
77 ms |
1244 KB |
Output is correct |
14 |
Correct |
87 ms |
1272 KB |
Output is correct |
15 |
Correct |
51 ms |
1400 KB |
Output is correct |
16 |
Correct |
34 ms |
1784 KB |
Output is correct |
17 |
Correct |
70 ms |
1400 KB |
Output is correct |
18 |
Correct |
68 ms |
1272 KB |
Output is correct |
19 |
Correct |
65 ms |
1272 KB |
Output is correct |
20 |
Correct |
59 ms |
1688 KB |
Output is correct |
21 |
Correct |
36 ms |
1528 KB |
Output is correct |
22 |
Correct |
38 ms |
1784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2422 ms |
52876 KB |
Output is correct |
2 |
Correct |
1016 ms |
52700 KB |
Output is correct |
3 |
Correct |
966 ms |
52856 KB |
Output is correct |
4 |
Correct |
899 ms |
52776 KB |
Output is correct |
5 |
Correct |
1041 ms |
52672 KB |
Output is correct |
6 |
Correct |
1022 ms |
52768 KB |
Output is correct |
7 |
Correct |
1033 ms |
52828 KB |
Output is correct |
8 |
Correct |
1055 ms |
52908 KB |
Output is correct |
9 |
Correct |
962 ms |
52752 KB |
Output is correct |
10 |
Correct |
973 ms |
52724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
1248 KB |
Output is correct |
2 |
Correct |
178 ms |
7060 KB |
Output is correct |
3 |
Correct |
902 ms |
52876 KB |
Output is correct |
4 |
Correct |
2346 ms |
52796 KB |
Output is correct |
5 |
Correct |
698 ms |
72496 KB |
Output is correct |
6 |
Correct |
2404 ms |
100984 KB |
Output is correct |
7 |
Correct |
1033 ms |
55216 KB |
Output is correct |
8 |
Correct |
1047 ms |
49036 KB |
Output is correct |
9 |
Correct |
1233 ms |
49120 KB |
Output is correct |
10 |
Correct |
1163 ms |
54996 KB |
Output is correct |
11 |
Correct |
998 ms |
79992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
1396 KB |
Output is correct |
2 |
Correct |
101 ms |
1396 KB |
Output is correct |
3 |
Correct |
170 ms |
1384 KB |
Output is correct |
4 |
Correct |
230 ms |
1524 KB |
Output is correct |
5 |
Correct |
447 ms |
2428 KB |
Output is correct |
6 |
Correct |
1357 ms |
69220 KB |
Output is correct |
7 |
Correct |
1617 ms |
69300 KB |
Output is correct |
8 |
Correct |
1126 ms |
69196 KB |
Output is correct |
9 |
Correct |
2595 ms |
69464 KB |
Output is correct |
10 |
Correct |
1244 ms |
69292 KB |
Output is correct |
11 |
Correct |
1234 ms |
69324 KB |
Output is correct |
12 |
Correct |
1053 ms |
69296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
632 KB |
Output is correct |
2 |
Correct |
26 ms |
504 KB |
Output is correct |
3 |
Correct |
41 ms |
376 KB |
Output is correct |
4 |
Correct |
23 ms |
504 KB |
Output is correct |
5 |
Correct |
18 ms |
504 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
38 ms |
504 KB |
Output is correct |
8 |
Correct |
31 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
31 ms |
632 KB |
Output is correct |
11 |
Correct |
34 ms |
632 KB |
Output is correct |
12 |
Correct |
18 ms |
504 KB |
Output is correct |
13 |
Correct |
77 ms |
1244 KB |
Output is correct |
14 |
Correct |
87 ms |
1272 KB |
Output is correct |
15 |
Correct |
51 ms |
1400 KB |
Output is correct |
16 |
Correct |
34 ms |
1784 KB |
Output is correct |
17 |
Correct |
70 ms |
1400 KB |
Output is correct |
18 |
Correct |
68 ms |
1272 KB |
Output is correct |
19 |
Correct |
65 ms |
1272 KB |
Output is correct |
20 |
Correct |
59 ms |
1688 KB |
Output is correct |
21 |
Correct |
36 ms |
1528 KB |
Output is correct |
22 |
Correct |
38 ms |
1784 KB |
Output is correct |
23 |
Correct |
2422 ms |
52876 KB |
Output is correct |
24 |
Correct |
1016 ms |
52700 KB |
Output is correct |
25 |
Correct |
966 ms |
52856 KB |
Output is correct |
26 |
Correct |
899 ms |
52776 KB |
Output is correct |
27 |
Correct |
1041 ms |
52672 KB |
Output is correct |
28 |
Correct |
1022 ms |
52768 KB |
Output is correct |
29 |
Correct |
1033 ms |
52828 KB |
Output is correct |
30 |
Correct |
1055 ms |
52908 KB |
Output is correct |
31 |
Correct |
962 ms |
52752 KB |
Output is correct |
32 |
Correct |
973 ms |
52724 KB |
Output is correct |
33 |
Correct |
79 ms |
1248 KB |
Output is correct |
34 |
Correct |
178 ms |
7060 KB |
Output is correct |
35 |
Correct |
902 ms |
52876 KB |
Output is correct |
36 |
Correct |
2346 ms |
52796 KB |
Output is correct |
37 |
Correct |
698 ms |
72496 KB |
Output is correct |
38 |
Correct |
2404 ms |
100984 KB |
Output is correct |
39 |
Correct |
1033 ms |
55216 KB |
Output is correct |
40 |
Correct |
1047 ms |
49036 KB |
Output is correct |
41 |
Correct |
1233 ms |
49120 KB |
Output is correct |
42 |
Correct |
1163 ms |
54996 KB |
Output is correct |
43 |
Correct |
998 ms |
79992 KB |
Output is correct |
44 |
Correct |
44 ms |
1396 KB |
Output is correct |
45 |
Correct |
101 ms |
1396 KB |
Output is correct |
46 |
Correct |
170 ms |
1384 KB |
Output is correct |
47 |
Correct |
230 ms |
1524 KB |
Output is correct |
48 |
Correct |
447 ms |
2428 KB |
Output is correct |
49 |
Correct |
1357 ms |
69220 KB |
Output is correct |
50 |
Correct |
1617 ms |
69300 KB |
Output is correct |
51 |
Correct |
1126 ms |
69196 KB |
Output is correct |
52 |
Correct |
2595 ms |
69464 KB |
Output is correct |
53 |
Correct |
1244 ms |
69292 KB |
Output is correct |
54 |
Correct |
1234 ms |
69324 KB |
Output is correct |
55 |
Correct |
1053 ms |
69296 KB |
Output is correct |
56 |
Correct |
156 ms |
1396 KB |
Output is correct |
57 |
Correct |
333 ms |
1408 KB |
Output is correct |
58 |
Correct |
542 ms |
2176 KB |
Output is correct |
59 |
Correct |
2155 ms |
49792 KB |
Output is correct |
60 |
Correct |
3712 ms |
49728 KB |
Output is correct |
61 |
Correct |
1682 ms |
66488 KB |
Output is correct |
62 |
Correct |
1413 ms |
76276 KB |
Output is correct |
63 |
Correct |
3538 ms |
72740 KB |
Output is correct |
64 |
Correct |
2158 ms |
68036 KB |
Output is correct |
65 |
Correct |
1864 ms |
66252 KB |
Output is correct |
66 |
Correct |
1983 ms |
66472 KB |
Output is correct |
67 |
Correct |
2176 ms |
72300 KB |
Output is correct |
68 |
Correct |
1648 ms |
85672 KB |
Output is correct |
69 |
Correct |
3696 ms |
97416 KB |
Output is correct |