# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
191314 |
2020-01-14T13:05:08 Z |
baluteshih |
Seats (IOI18_seats) |
C++14 |
|
1918 ms |
123256 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
struct node {
int min_val, min_cnt, lazy_tag;
}tr[MAXN * 4];
pair<int, int> seat[MAXN];
vector<vector<int>> mp;
int tags[MAXN], type, HW;
int dx[4] = {0, -1, 0 ,-1}, dy[4] = {0, 0, -1, -1};
void merge(node &u, node lch, node rch) {
if(lch.min_val > rch.min_val)
swap(lch,rch);
u.min_val = lch.min_val;
u.min_cnt = lch.min_cnt;
if(lch.min_val == rch.min_val)
u.min_cnt += rch.min_cnt;
}
void push_down(node &u, node &lch, node &rch) {
lch.min_val += u.lazy_tag;
lch.lazy_tag += u.lazy_tag;
rch.min_val += u.lazy_tag;
rch.lazy_tag += u.lazy_tag;
u.lazy_tag = 0;
}
void build(int idx, int lb, int rb) {
if(lb == rb) {
tr[idx].min_val = tags[lb];
tr[idx].min_cnt = 1;
tr[idx].lazy_tag = 0;
return;
}
int mid = (lb + rb) / 2;
build(idx * 2, lb, mid);
build(idx * 2 + 1, mid + 1, rb);
merge(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
}
void modify(int idx, int lb, int rb, int ql, int qr, int val) {
if(ql <= lb && rb <= qr) {
tr[idx].min_val += val;
tr[idx].lazy_tag += val;
return;
}
push_down(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
int mid = (lb + rb) / 2;
if(ql <= mid)
modify(idx * 2, lb, mid, ql, qr, val);
if(qr > mid)
modify(idx * 2 + 1, mid + 1, rb, ql, qr, val);
merge(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
}
void add_segment(int lb, int rb, int val) {
if(lb == rb) return;
if(type == 0) {
tags[lb] += val;
tags[rb] -= val;
}
else
modify(1, 1, HW, lb, rb - 1, val);
}
void pattern(int x, int y, int val) {
int a[4] = {mp[x][y], mp[x+1][y], mp[x][y+1], mp[x+1][y+1]};
sort(a, a + 4);
add_segment(a[0], a[1], val);
add_segment(a[2], a[3], val);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
HW = H * W;
mp.resize(H + 2, vector<int>(W + 2, HW + 1));
for(int i = 0; i < HW; ++i) {
mp[R[i] + 1][C[i] + 1] = i + 1;
seat[i + 1] = make_pair(R[i] + 1, C[i] + 1);
}
for(int i = 0; i <= H; ++i)
for(int j = 0; j <= W; ++j)
pattern(i, j, 1);
for(int i = 1; i <= HW; ++i)
tags[i] += tags[i-1];
build(1, 1, HW);
type = 1;
}
//swap_seats會回傳每次交換完的美麗程度
int swap_seats(int a, int b) {
++a, ++b;
for(int i = 0; i < 4; ++i)
pattern(seat[a].first + dx[i], seat[a].second + dy[i], -1);
mp[seat[a].first][seat[a].second] = b;
for(int i = 0; i < 4; ++i)
pattern(seat[a].first + dx[i], seat[a].second + dy[i], 1);
for(int i = 0; i < 4; ++i)
pattern(seat[b].first + dx[i], seat[b].second + dy[i], -1);
mp[seat[b].first][seat[b].second] = a;
for(int i = 0; i < 4; ++i)
pattern(seat[b].first + dx[i], seat[b].second + dy[i], 1);
swap(seat[a], seat[b]);
return tr[1].min_cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
504 KB |
Output is correct |
2 |
Correct |
20 ms |
504 KB |
Output is correct |
3 |
Correct |
26 ms |
504 KB |
Output is correct |
4 |
Correct |
22 ms |
632 KB |
Output is correct |
5 |
Correct |
19 ms |
504 KB |
Output is correct |
6 |
Correct |
22 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
520 KB |
Output is correct |
8 |
Correct |
28 ms |
504 KB |
Output is correct |
9 |
Correct |
31 ms |
504 KB |
Output is correct |
10 |
Correct |
29 ms |
504 KB |
Output is correct |
11 |
Correct |
28 ms |
504 KB |
Output is correct |
12 |
Correct |
20 ms |
516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
504 KB |
Output is correct |
2 |
Correct |
20 ms |
504 KB |
Output is correct |
3 |
Correct |
26 ms |
504 KB |
Output is correct |
4 |
Correct |
22 ms |
632 KB |
Output is correct |
5 |
Correct |
19 ms |
504 KB |
Output is correct |
6 |
Correct |
22 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
520 KB |
Output is correct |
8 |
Correct |
28 ms |
504 KB |
Output is correct |
9 |
Correct |
31 ms |
504 KB |
Output is correct |
10 |
Correct |
29 ms |
504 KB |
Output is correct |
11 |
Correct |
28 ms |
504 KB |
Output is correct |
12 |
Correct |
20 ms |
516 KB |
Output is correct |
13 |
Correct |
71 ms |
1400 KB |
Output is correct |
14 |
Correct |
75 ms |
1332 KB |
Output is correct |
15 |
Correct |
44 ms |
1400 KB |
Output is correct |
16 |
Correct |
38 ms |
1912 KB |
Output is correct |
17 |
Correct |
56 ms |
1272 KB |
Output is correct |
18 |
Correct |
55 ms |
1272 KB |
Output is correct |
19 |
Correct |
52 ms |
1400 KB |
Output is correct |
20 |
Correct |
47 ms |
1528 KB |
Output is correct |
21 |
Correct |
36 ms |
1400 KB |
Output is correct |
22 |
Correct |
38 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
615 ms |
72456 KB |
Output is correct |
2 |
Correct |
485 ms |
72440 KB |
Output is correct |
3 |
Correct |
487 ms |
72428 KB |
Output is correct |
4 |
Correct |
468 ms |
72312 KB |
Output is correct |
5 |
Correct |
473 ms |
72312 KB |
Output is correct |
6 |
Correct |
469 ms |
72284 KB |
Output is correct |
7 |
Correct |
477 ms |
72200 KB |
Output is correct |
8 |
Correct |
489 ms |
72312 KB |
Output is correct |
9 |
Correct |
477 ms |
72488 KB |
Output is correct |
10 |
Correct |
472 ms |
72568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
1272 KB |
Output is correct |
2 |
Correct |
112 ms |
7544 KB |
Output is correct |
3 |
Correct |
447 ms |
72324 KB |
Output is correct |
4 |
Correct |
607 ms |
72432 KB |
Output is correct |
5 |
Correct |
440 ms |
80196 KB |
Output is correct |
6 |
Correct |
823 ms |
123256 KB |
Output is correct |
7 |
Correct |
460 ms |
74976 KB |
Output is correct |
8 |
Correct |
479 ms |
72412 KB |
Output is correct |
9 |
Correct |
492 ms |
72796 KB |
Output is correct |
10 |
Correct |
484 ms |
76932 KB |
Output is correct |
11 |
Correct |
487 ms |
95780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
2036 KB |
Output is correct |
2 |
Correct |
96 ms |
2164 KB |
Output is correct |
3 |
Correct |
170 ms |
2292 KB |
Output is correct |
4 |
Correct |
230 ms |
2164 KB |
Output is correct |
5 |
Correct |
375 ms |
3020 KB |
Output is correct |
6 |
Correct |
942 ms |
81200 KB |
Output is correct |
7 |
Correct |
1014 ms |
81004 KB |
Output is correct |
8 |
Correct |
960 ms |
81120 KB |
Output is correct |
9 |
Correct |
1253 ms |
81088 KB |
Output is correct |
10 |
Correct |
895 ms |
81200 KB |
Output is correct |
11 |
Correct |
898 ms |
81084 KB |
Output is correct |
12 |
Correct |
851 ms |
81200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
504 KB |
Output is correct |
2 |
Correct |
20 ms |
504 KB |
Output is correct |
3 |
Correct |
26 ms |
504 KB |
Output is correct |
4 |
Correct |
22 ms |
632 KB |
Output is correct |
5 |
Correct |
19 ms |
504 KB |
Output is correct |
6 |
Correct |
22 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
520 KB |
Output is correct |
8 |
Correct |
28 ms |
504 KB |
Output is correct |
9 |
Correct |
31 ms |
504 KB |
Output is correct |
10 |
Correct |
29 ms |
504 KB |
Output is correct |
11 |
Correct |
28 ms |
504 KB |
Output is correct |
12 |
Correct |
20 ms |
516 KB |
Output is correct |
13 |
Correct |
71 ms |
1400 KB |
Output is correct |
14 |
Correct |
75 ms |
1332 KB |
Output is correct |
15 |
Correct |
44 ms |
1400 KB |
Output is correct |
16 |
Correct |
38 ms |
1912 KB |
Output is correct |
17 |
Correct |
56 ms |
1272 KB |
Output is correct |
18 |
Correct |
55 ms |
1272 KB |
Output is correct |
19 |
Correct |
52 ms |
1400 KB |
Output is correct |
20 |
Correct |
47 ms |
1528 KB |
Output is correct |
21 |
Correct |
36 ms |
1400 KB |
Output is correct |
22 |
Correct |
38 ms |
1912 KB |
Output is correct |
23 |
Correct |
615 ms |
72456 KB |
Output is correct |
24 |
Correct |
485 ms |
72440 KB |
Output is correct |
25 |
Correct |
487 ms |
72428 KB |
Output is correct |
26 |
Correct |
468 ms |
72312 KB |
Output is correct |
27 |
Correct |
473 ms |
72312 KB |
Output is correct |
28 |
Correct |
469 ms |
72284 KB |
Output is correct |
29 |
Correct |
477 ms |
72200 KB |
Output is correct |
30 |
Correct |
489 ms |
72312 KB |
Output is correct |
31 |
Correct |
477 ms |
72488 KB |
Output is correct |
32 |
Correct |
472 ms |
72568 KB |
Output is correct |
33 |
Correct |
70 ms |
1272 KB |
Output is correct |
34 |
Correct |
112 ms |
7544 KB |
Output is correct |
35 |
Correct |
447 ms |
72324 KB |
Output is correct |
36 |
Correct |
607 ms |
72432 KB |
Output is correct |
37 |
Correct |
440 ms |
80196 KB |
Output is correct |
38 |
Correct |
823 ms |
123256 KB |
Output is correct |
39 |
Correct |
460 ms |
74976 KB |
Output is correct |
40 |
Correct |
479 ms |
72412 KB |
Output is correct |
41 |
Correct |
492 ms |
72796 KB |
Output is correct |
42 |
Correct |
484 ms |
76932 KB |
Output is correct |
43 |
Correct |
487 ms |
95780 KB |
Output is correct |
44 |
Correct |
54 ms |
2036 KB |
Output is correct |
45 |
Correct |
96 ms |
2164 KB |
Output is correct |
46 |
Correct |
170 ms |
2292 KB |
Output is correct |
47 |
Correct |
230 ms |
2164 KB |
Output is correct |
48 |
Correct |
375 ms |
3020 KB |
Output is correct |
49 |
Correct |
942 ms |
81200 KB |
Output is correct |
50 |
Correct |
1014 ms |
81004 KB |
Output is correct |
51 |
Correct |
960 ms |
81120 KB |
Output is correct |
52 |
Correct |
1253 ms |
81088 KB |
Output is correct |
53 |
Correct |
895 ms |
81200 KB |
Output is correct |
54 |
Correct |
898 ms |
81084 KB |
Output is correct |
55 |
Correct |
851 ms |
81200 KB |
Output is correct |
56 |
Correct |
108 ms |
2224 KB |
Output is correct |
57 |
Correct |
306 ms |
2036 KB |
Output is correct |
58 |
Correct |
506 ms |
3140 KB |
Output is correct |
59 |
Correct |
1385 ms |
73336 KB |
Output is correct |
60 |
Correct |
1918 ms |
73336 KB |
Output is correct |
61 |
Correct |
1203 ms |
73336 KB |
Output is correct |
62 |
Correct |
1040 ms |
77140 KB |
Output is correct |
63 |
Correct |
1795 ms |
75876 KB |
Output is correct |
64 |
Correct |
1324 ms |
74096 KB |
Output is correct |
65 |
Correct |
1180 ms |
73464 KB |
Output is correct |
66 |
Correct |
1419 ms |
73720 KB |
Output is correct |
67 |
Correct |
1342 ms |
77944 KB |
Output is correct |
68 |
Correct |
1103 ms |
87556 KB |
Output is correct |
69 |
Correct |
1700 ms |
96796 KB |
Output is correct |