# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
103047 |
2019-03-28T21:05:52 Z |
KCSC |
Seats (IOI18_seats) |
C++14 |
|
2439 ms |
129688 KB |
#ifndef HOME
#include "seats.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#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
#endif
const int DIM = 1000005;
struct Node {
int mnm, cnt, lzy;
Node(int _mnm = 0, int _cnt = 0, int _lzy = 0) :
mnm(_mnm), cnt(_cnt), lzy(_lzy) {}
} sgt[DIM << 2];
vector<vector<int>> mat;
pair<int, int> pos[DIM];
int n, m, psm[DIM];
void build(int nd, int le, int ri) {
if (le == ri) {
sgt[nd] = Node(psm[le], 1); }
else {
int md = (le + ri) >> 1;
build(nd << 1, le, md);
build(nd << 1 | 1, md + 1, ri);
sgt[nd].mnm = min(sgt[nd << 1].mnm, sgt[nd << 1 | 1].mnm);
if (sgt[nd].mnm == sgt[nd << 1].mnm) {
sgt[nd].cnt += sgt[nd << 1].cnt; }
if (sgt[nd].mnm == sgt[nd << 1 | 1].mnm) {
sgt[nd].cnt += sgt[nd << 1 | 1].cnt; } } }
int _st, _en, _vl;
void update(int nd, int le, int ri) {
if (sgt[nd].lzy) {
sgt[nd].mnm += sgt[nd].lzy;
if (le != ri) {
sgt[nd << 1].lzy += sgt[nd].lzy;
sgt[nd << 1 | 1].lzy += sgt[nd].lzy; }
sgt[nd].lzy = 0; }
if (ri < _st or _en < le or _st > _en) {
return; }
if (_st <= le and ri <= _en) {
sgt[nd].mnm += _vl;
if (le != ri) {
sgt[nd << 1].lzy += _vl;
sgt[nd << 1 | 1].lzy += _vl; } }
else {
int md = (le + ri) >> 1;
update(nd << 1, le, md);
update(nd << 1 | 1, md + 1, ri);
sgt[nd].mnm = min(sgt[nd << 1].mnm, sgt[nd << 1 | 1].mnm);
sgt[nd].cnt = 0;
if (sgt[nd].mnm == sgt[nd << 1].mnm) {
sgt[nd].cnt += sgt[nd << 1].cnt; }
if (sgt[nd].mnm == sgt[nd << 1 | 1].mnm) {
sgt[nd].cnt += sgt[nd << 1 | 1].cnt; } } }
void updateSquare(int x, int y, int vl = 1, bool ok = true) {
vector<int> arr;
arr.push_back(mat[x][y]); arr.push_back(mat[x + 1][y + 1]);
arr.push_back(mat[x][y + 1]); arr.push_back(mat[x + 1][y]);
sort(arr.begin(), arr.end());
if (ok) {
_st = arr[0]; _en = arr[1] - 1; _vl = vl * 1;
update(1, 0, n * m - 1);
_st = arr[2]; _en = arr[3] - 1; _vl = vl * 5;
update(1, 0, n * m - 1); }
else {
psm[arr[0]] += vl * 1; psm[arr[1]] -= vl * 1;
psm[arr[2]] += vl * 5; psm[arr[3]] -= vl * 5; } }
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
n = h; m = w;
mat.resize(n + 2, vector<int>(m + 2, n * m));
for (int i = 0; i < n * m; ++i) {
++R[i]; ++C[i]; mat[R[i]][C[i]] = i;
pos[i] = make_pair(R[i], C[i]); }
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
updateSquare(i, j, 1, false); } }
for (int i = 1; i < n * m; ++i) {
psm[i] += psm[i - 1]; }
build(1, 0, n * m - 1); }
int swap_seats(int a, int b) {
set<pair<int, int>> sqr;
for (int i = -1; i <= 0; ++i) {
for (int j = -1; j <= 0; ++j) {
sqr.insert(make_pair(pos[a].first + i, pos[a].second + j));
sqr.insert(make_pair(pos[b].first + i, pos[b].second + j)); } }
for (auto sq : sqr) {
updateSquare(sq.first, sq.second, -1); }
swap(mat[pos[a].first][pos[a].second], mat[pos[b].first][pos[b].second]);
swap(pos[a], pos[b]);
for (auto sq : sqr) {
updateSquare(sq.first, sq.second, 1); }
return sgt[1].mnm == 4 ? sgt[1].cnt : 0; }
#ifdef HOME
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 |
71 ms |
47528 KB |
Output is correct |
2 |
Correct |
80 ms |
47396 KB |
Output is correct |
3 |
Correct |
87 ms |
47408 KB |
Output is correct |
4 |
Correct |
83 ms |
47480 KB |
Output is correct |
5 |
Correct |
71 ms |
47352 KB |
Output is correct |
6 |
Correct |
82 ms |
47456 KB |
Output is correct |
7 |
Correct |
82 ms |
47452 KB |
Output is correct |
8 |
Correct |
86 ms |
47324 KB |
Output is correct |
9 |
Correct |
85 ms |
47452 KB |
Output is correct |
10 |
Correct |
102 ms |
47480 KB |
Output is correct |
11 |
Correct |
88 ms |
47480 KB |
Output is correct |
12 |
Correct |
73 ms |
47480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
47528 KB |
Output is correct |
2 |
Correct |
80 ms |
47396 KB |
Output is correct |
3 |
Correct |
87 ms |
47408 KB |
Output is correct |
4 |
Correct |
83 ms |
47480 KB |
Output is correct |
5 |
Correct |
71 ms |
47352 KB |
Output is correct |
6 |
Correct |
82 ms |
47456 KB |
Output is correct |
7 |
Correct |
82 ms |
47452 KB |
Output is correct |
8 |
Correct |
86 ms |
47324 KB |
Output is correct |
9 |
Correct |
85 ms |
47452 KB |
Output is correct |
10 |
Correct |
102 ms |
47480 KB |
Output is correct |
11 |
Correct |
88 ms |
47480 KB |
Output is correct |
12 |
Correct |
73 ms |
47480 KB |
Output is correct |
13 |
Correct |
135 ms |
47708 KB |
Output is correct |
14 |
Correct |
150 ms |
47732 KB |
Output is correct |
15 |
Correct |
124 ms |
47864 KB |
Output is correct |
16 |
Correct |
90 ms |
48248 KB |
Output is correct |
17 |
Correct |
126 ms |
47748 KB |
Output is correct |
18 |
Correct |
119 ms |
47736 KB |
Output is correct |
19 |
Correct |
108 ms |
47844 KB |
Output is correct |
20 |
Correct |
106 ms |
47952 KB |
Output is correct |
21 |
Correct |
91 ms |
47844 KB |
Output is correct |
22 |
Correct |
90 ms |
48248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
926 ms |
78720 KB |
Output is correct |
2 |
Correct |
645 ms |
78840 KB |
Output is correct |
3 |
Correct |
799 ms |
78684 KB |
Output is correct |
4 |
Correct |
690 ms |
78840 KB |
Output is correct |
5 |
Correct |
796 ms |
78840 KB |
Output is correct |
6 |
Correct |
578 ms |
78840 KB |
Output is correct |
7 |
Correct |
648 ms |
78712 KB |
Output is correct |
8 |
Correct |
607 ms |
78840 KB |
Output is correct |
9 |
Correct |
595 ms |
78712 KB |
Output is correct |
10 |
Correct |
595 ms |
78684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
47608 KB |
Output is correct |
2 |
Correct |
181 ms |
50168 KB |
Output is correct |
3 |
Correct |
571 ms |
78840 KB |
Output is correct |
4 |
Correct |
838 ms |
78968 KB |
Output is correct |
5 |
Correct |
662 ms |
86576 KB |
Output is correct |
6 |
Correct |
1193 ms |
129688 KB |
Output is correct |
7 |
Correct |
716 ms |
81388 KB |
Output is correct |
8 |
Correct |
742 ms |
78840 KB |
Output is correct |
9 |
Correct |
615 ms |
79100 KB |
Output is correct |
10 |
Correct |
672 ms |
83448 KB |
Output is correct |
11 |
Correct |
745 ms |
102184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
48392 KB |
Output is correct |
2 |
Correct |
287 ms |
48400 KB |
Output is correct |
3 |
Correct |
386 ms |
48528 KB |
Output is correct |
4 |
Correct |
421 ms |
48328 KB |
Output is correct |
5 |
Correct |
637 ms |
48952 KB |
Output is correct |
6 |
Correct |
1427 ms |
86964 KB |
Output is correct |
7 |
Correct |
1503 ms |
86832 KB |
Output is correct |
8 |
Correct |
1398 ms |
87216 KB |
Output is correct |
9 |
Correct |
1925 ms |
86960 KB |
Output is correct |
10 |
Correct |
1335 ms |
86908 KB |
Output is correct |
11 |
Correct |
1201 ms |
87092 KB |
Output is correct |
12 |
Correct |
1294 ms |
86960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
47528 KB |
Output is correct |
2 |
Correct |
80 ms |
47396 KB |
Output is correct |
3 |
Correct |
87 ms |
47408 KB |
Output is correct |
4 |
Correct |
83 ms |
47480 KB |
Output is correct |
5 |
Correct |
71 ms |
47352 KB |
Output is correct |
6 |
Correct |
82 ms |
47456 KB |
Output is correct |
7 |
Correct |
82 ms |
47452 KB |
Output is correct |
8 |
Correct |
86 ms |
47324 KB |
Output is correct |
9 |
Correct |
85 ms |
47452 KB |
Output is correct |
10 |
Correct |
102 ms |
47480 KB |
Output is correct |
11 |
Correct |
88 ms |
47480 KB |
Output is correct |
12 |
Correct |
73 ms |
47480 KB |
Output is correct |
13 |
Correct |
135 ms |
47708 KB |
Output is correct |
14 |
Correct |
150 ms |
47732 KB |
Output is correct |
15 |
Correct |
124 ms |
47864 KB |
Output is correct |
16 |
Correct |
90 ms |
48248 KB |
Output is correct |
17 |
Correct |
126 ms |
47748 KB |
Output is correct |
18 |
Correct |
119 ms |
47736 KB |
Output is correct |
19 |
Correct |
108 ms |
47844 KB |
Output is correct |
20 |
Correct |
106 ms |
47952 KB |
Output is correct |
21 |
Correct |
91 ms |
47844 KB |
Output is correct |
22 |
Correct |
90 ms |
48248 KB |
Output is correct |
23 |
Correct |
926 ms |
78720 KB |
Output is correct |
24 |
Correct |
645 ms |
78840 KB |
Output is correct |
25 |
Correct |
799 ms |
78684 KB |
Output is correct |
26 |
Correct |
690 ms |
78840 KB |
Output is correct |
27 |
Correct |
796 ms |
78840 KB |
Output is correct |
28 |
Correct |
578 ms |
78840 KB |
Output is correct |
29 |
Correct |
648 ms |
78712 KB |
Output is correct |
30 |
Correct |
607 ms |
78840 KB |
Output is correct |
31 |
Correct |
595 ms |
78712 KB |
Output is correct |
32 |
Correct |
595 ms |
78684 KB |
Output is correct |
33 |
Correct |
123 ms |
47608 KB |
Output is correct |
34 |
Correct |
181 ms |
50168 KB |
Output is correct |
35 |
Correct |
571 ms |
78840 KB |
Output is correct |
36 |
Correct |
838 ms |
78968 KB |
Output is correct |
37 |
Correct |
662 ms |
86576 KB |
Output is correct |
38 |
Correct |
1193 ms |
129688 KB |
Output is correct |
39 |
Correct |
716 ms |
81388 KB |
Output is correct |
40 |
Correct |
742 ms |
78840 KB |
Output is correct |
41 |
Correct |
615 ms |
79100 KB |
Output is correct |
42 |
Correct |
672 ms |
83448 KB |
Output is correct |
43 |
Correct |
745 ms |
102184 KB |
Output is correct |
44 |
Correct |
210 ms |
48392 KB |
Output is correct |
45 |
Correct |
287 ms |
48400 KB |
Output is correct |
46 |
Correct |
386 ms |
48528 KB |
Output is correct |
47 |
Correct |
421 ms |
48328 KB |
Output is correct |
48 |
Correct |
637 ms |
48952 KB |
Output is correct |
49 |
Correct |
1427 ms |
86964 KB |
Output is correct |
50 |
Correct |
1503 ms |
86832 KB |
Output is correct |
51 |
Correct |
1398 ms |
87216 KB |
Output is correct |
52 |
Correct |
1925 ms |
86960 KB |
Output is correct |
53 |
Correct |
1335 ms |
86908 KB |
Output is correct |
54 |
Correct |
1201 ms |
87092 KB |
Output is correct |
55 |
Correct |
1294 ms |
86960 KB |
Output is correct |
56 |
Correct |
351 ms |
48424 KB |
Output is correct |
57 |
Correct |
540 ms |
48452 KB |
Output is correct |
58 |
Correct |
767 ms |
48820 KB |
Output is correct |
59 |
Correct |
1920 ms |
79096 KB |
Output is correct |
60 |
Correct |
2439 ms |
79224 KB |
Output is correct |
61 |
Correct |
1437 ms |
85368 KB |
Output is correct |
62 |
Correct |
1305 ms |
89556 KB |
Output is correct |
63 |
Correct |
2206 ms |
87780 KB |
Output is correct |
64 |
Correct |
1851 ms |
85104 KB |
Output is correct |
65 |
Correct |
1439 ms |
85368 KB |
Output is correct |
66 |
Correct |
1881 ms |
85368 KB |
Output is correct |
67 |
Correct |
1701 ms |
89884 KB |
Output is correct |
68 |
Correct |
1344 ms |
99576 KB |
Output is correct |
69 |
Correct |
2185 ms |
108536 KB |
Output is correct |