# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
256859 |
2020-08-03T09:53:27 Z |
Hehehe |
Seats (IOI18_seats) |
C++14 |
|
2866 ms |
131064 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
using namespace std;
const int NMAX = 4000005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
typedef pair<int, int> pii;
pii t[4*NMAX];
int lz[4*NMAX];
pii seats[4000555];
int tsz, H, W;
void updateA(pii pos);
void deleteA(pii pos);
void updateB(pii pos);
void deleteB(pii pos);
int secondSmallestNeighbour(pii pos);
pii getB(pii pos);
bool ok(pii pos);
void rewrite(pii pos, int val);
vector<vector<int>> arr;
int ln(int n){
return 2*n;
}
int rn(int n){
return 2*n + 1;
}
pii merge(pii a, pii b){
if(a.ff < b.ff)return a;
if(a.ff > b.ff)return b;
return {a.ff, a.ss + b.ss};
}
void push(int v){
if(!lz[v])return;
t[2*v].ff += lz[v];
t[2*v + 1].ff += lz[v];
lz[2*v] += lz[v];
lz[2*v + 1] += lz[v];
lz[v] = 0;
}
void build(int v, int l, int r){
if(l == r){
t[v] = {0, 1};
return;
}
int mid = (l + r) >> 1;
build(2*v, l, mid);
build(2*v + 1, mid + 1, r);
t[v] = merge(t[2*v], t[2*v + 1]);
}
void update(int v, int tl, int tr, int l, int r, int add){
push(v);
if(tl > r || tr < l)return;
if(l <= tl && tr <= r){
lz[v] += add;
t[v].ff += add;
push(v);
return;
}
push(v);
int mid = (tl + tr) >> 1;
if(l <= mid)update(2*v, tl, mid, l, r, add);
if(r > mid)update(2*v + 1, mid + 1, tr, l, r, add);
t[v] = merge(t[2*v], t[2*v + 1]);
}
void give_initial_chart(int HH, int WW, vector<int> R, vector<int> C) {
W = WW;
H = HH;
tsz = H*W;
build(1, 1, tsz);
arr = vector<vector<int>>(H+1, vector<int>(W+1, 0));
for(int i=0; i<H*W; ++i){
arr[R[i] + 1][C[i] + 1] = i + 1;
seats[i] = {R[i] + 1, C[i] + 1};
}
for(int i = 1; i<=H; ++i){
for(int j = 1; j<=W; ++j){
updateA({i, j});
updateB({i, j});
}
}
}
int swap_seats(int a, int b){
rewrite(seats[a], b + 1);
rewrite(seats[b], a + 1);
swap(seats[a], seats[b]);
return (t[1].first == 1 ? t[1].second : 0);
}
void rewrite(pii pos, int val){
deleteA(pos);
for(int i = 0; i < 4; ++i){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux)){
deleteA(aux);
}
}
deleteB(pos);
for(int i=2; i<4; ++i){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux)){
deleteB(aux);
}
}
arr[pos.x][pos.y] = val;
updateA(pos);
for(int i=0; i<4; ++i){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux)){
updateA(aux);
}
}
updateB(pos);
for(int i=2; i<4; ++i){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux)){
updateB(aux);
}
}
}
void deleteA(pii pos){
int l = secondSmallestNeighbour(pos);
int r = arr[pos.x][pos.y];
if(r > l){
update(1, 1, tsz, l, r - 1, -1);
}
}
void updateA(pii pos){
int l = secondSmallestNeighbour(pos);
int r = arr[pos.x][pos.y];
if(r > l){
update(1, 1, tsz, l, r - 1, +1);
}
}
void deleteB(pii pos){
pii p = getB(pos);
if(p.y > p.x){
update(1, 1, tsz, p.x, p.y - 1, -1);
}
}
void updateB(pii pos){
pii p = getB(pos);
if(p.y > p.x){
update(1, 1, tsz, p.x, p.y - 1, +1);
}
}
int secondSmallestNeighbour(pii pos){
vector<int>s;
for(int i = 0; i < 4; i++){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux))s.push_back(arr[aux.x][aux.y]);
}
sort(all(s));
if(s.size() > 1)return s[1];
return tsz+1;
}
pii getB(pii pos){
int l = arr[pos.x][pos.y];
int r = tsz + 1;
for(int i=0; i<4; ++i){
pii aux = pos;
aux.x += dx[i];
aux.y += dy[i];
if(ok(aux)){
if(i < 2)
r = min(r, arr[aux.x][aux.y]);
}
}
return {l, r};
}
bool ok(pii pos){
if(pos.x <= 0 || pos.x > H || pos.y <= 0 || pos.y > W)return 0;
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
28 ms |
512 KB |
Output is correct |
3 |
Correct |
39 ms |
512 KB |
Output is correct |
4 |
Correct |
20 ms |
512 KB |
Output is correct |
5 |
Correct |
18 ms |
512 KB |
Output is correct |
6 |
Correct |
32 ms |
512 KB |
Output is correct |
7 |
Correct |
36 ms |
512 KB |
Output is correct |
8 |
Correct |
35 ms |
512 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
33 ms |
512 KB |
Output is correct |
12 |
Correct |
18 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
28 ms |
512 KB |
Output is correct |
3 |
Correct |
39 ms |
512 KB |
Output is correct |
4 |
Correct |
20 ms |
512 KB |
Output is correct |
5 |
Correct |
18 ms |
512 KB |
Output is correct |
6 |
Correct |
32 ms |
512 KB |
Output is correct |
7 |
Correct |
36 ms |
512 KB |
Output is correct |
8 |
Correct |
35 ms |
512 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
33 ms |
512 KB |
Output is correct |
12 |
Correct |
18 ms |
512 KB |
Output is correct |
13 |
Correct |
75 ms |
1656 KB |
Output is correct |
14 |
Correct |
74 ms |
1656 KB |
Output is correct |
15 |
Correct |
43 ms |
1664 KB |
Output is correct |
16 |
Correct |
31 ms |
2176 KB |
Output is correct |
17 |
Correct |
53 ms |
1664 KB |
Output is correct |
18 |
Correct |
63 ms |
1656 KB |
Output is correct |
19 |
Correct |
51 ms |
1664 KB |
Output is correct |
20 |
Correct |
39 ms |
1792 KB |
Output is correct |
21 |
Correct |
32 ms |
1664 KB |
Output is correct |
22 |
Correct |
32 ms |
2176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1785 ms |
81272 KB |
Output is correct |
2 |
Correct |
1106 ms |
80376 KB |
Output is correct |
3 |
Correct |
981 ms |
80376 KB |
Output is correct |
4 |
Correct |
910 ms |
78456 KB |
Output is correct |
5 |
Correct |
1049 ms |
80376 KB |
Output is correct |
6 |
Correct |
918 ms |
78456 KB |
Output is correct |
7 |
Correct |
976 ms |
80468 KB |
Output is correct |
8 |
Correct |
1004 ms |
78336 KB |
Output is correct |
9 |
Correct |
874 ms |
80324 KB |
Output is correct |
10 |
Correct |
988 ms |
80376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
1664 KB |
Output is correct |
2 |
Correct |
183 ms |
10360 KB |
Output is correct |
3 |
Correct |
845 ms |
79864 KB |
Output is correct |
4 |
Correct |
1881 ms |
80504 KB |
Output is correct |
5 |
Correct |
555 ms |
70832 KB |
Output is correct |
6 |
Correct |
1655 ms |
131064 KB |
Output is correct |
7 |
Correct |
995 ms |
80992 KB |
Output is correct |
8 |
Correct |
954 ms |
80248 KB |
Output is correct |
9 |
Correct |
1038 ms |
78588 KB |
Output is correct |
10 |
Correct |
1105 ms |
84728 KB |
Output is correct |
11 |
Correct |
941 ms |
101496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
2036 KB |
Output is correct |
2 |
Correct |
132 ms |
2068 KB |
Output is correct |
3 |
Correct |
174 ms |
2036 KB |
Output is correct |
4 |
Correct |
207 ms |
2168 KB |
Output is correct |
5 |
Correct |
316 ms |
3188 KB |
Output is correct |
6 |
Correct |
1194 ms |
79540 KB |
Output is correct |
7 |
Correct |
1286 ms |
81896 KB |
Output is correct |
8 |
Correct |
870 ms |
74528 KB |
Output is correct |
9 |
Correct |
1997 ms |
81584 KB |
Output is correct |
10 |
Correct |
1132 ms |
80432 KB |
Output is correct |
11 |
Correct |
1038 ms |
80560 KB |
Output is correct |
12 |
Correct |
1126 ms |
79536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
28 ms |
512 KB |
Output is correct |
3 |
Correct |
39 ms |
512 KB |
Output is correct |
4 |
Correct |
20 ms |
512 KB |
Output is correct |
5 |
Correct |
18 ms |
512 KB |
Output is correct |
6 |
Correct |
32 ms |
512 KB |
Output is correct |
7 |
Correct |
36 ms |
512 KB |
Output is correct |
8 |
Correct |
35 ms |
512 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
35 ms |
512 KB |
Output is correct |
11 |
Correct |
33 ms |
512 KB |
Output is correct |
12 |
Correct |
18 ms |
512 KB |
Output is correct |
13 |
Correct |
75 ms |
1656 KB |
Output is correct |
14 |
Correct |
74 ms |
1656 KB |
Output is correct |
15 |
Correct |
43 ms |
1664 KB |
Output is correct |
16 |
Correct |
31 ms |
2176 KB |
Output is correct |
17 |
Correct |
53 ms |
1664 KB |
Output is correct |
18 |
Correct |
63 ms |
1656 KB |
Output is correct |
19 |
Correct |
51 ms |
1664 KB |
Output is correct |
20 |
Correct |
39 ms |
1792 KB |
Output is correct |
21 |
Correct |
32 ms |
1664 KB |
Output is correct |
22 |
Correct |
32 ms |
2176 KB |
Output is correct |
23 |
Correct |
1785 ms |
81272 KB |
Output is correct |
24 |
Correct |
1106 ms |
80376 KB |
Output is correct |
25 |
Correct |
981 ms |
80376 KB |
Output is correct |
26 |
Correct |
910 ms |
78456 KB |
Output is correct |
27 |
Correct |
1049 ms |
80376 KB |
Output is correct |
28 |
Correct |
918 ms |
78456 KB |
Output is correct |
29 |
Correct |
976 ms |
80468 KB |
Output is correct |
30 |
Correct |
1004 ms |
78336 KB |
Output is correct |
31 |
Correct |
874 ms |
80324 KB |
Output is correct |
32 |
Correct |
988 ms |
80376 KB |
Output is correct |
33 |
Correct |
76 ms |
1664 KB |
Output is correct |
34 |
Correct |
183 ms |
10360 KB |
Output is correct |
35 |
Correct |
845 ms |
79864 KB |
Output is correct |
36 |
Correct |
1881 ms |
80504 KB |
Output is correct |
37 |
Correct |
555 ms |
70832 KB |
Output is correct |
38 |
Correct |
1655 ms |
131064 KB |
Output is correct |
39 |
Correct |
995 ms |
80992 KB |
Output is correct |
40 |
Correct |
954 ms |
80248 KB |
Output is correct |
41 |
Correct |
1038 ms |
78588 KB |
Output is correct |
42 |
Correct |
1105 ms |
84728 KB |
Output is correct |
43 |
Correct |
941 ms |
101496 KB |
Output is correct |
44 |
Correct |
85 ms |
2036 KB |
Output is correct |
45 |
Correct |
132 ms |
2068 KB |
Output is correct |
46 |
Correct |
174 ms |
2036 KB |
Output is correct |
47 |
Correct |
207 ms |
2168 KB |
Output is correct |
48 |
Correct |
316 ms |
3188 KB |
Output is correct |
49 |
Correct |
1194 ms |
79540 KB |
Output is correct |
50 |
Correct |
1286 ms |
81896 KB |
Output is correct |
51 |
Correct |
870 ms |
74528 KB |
Output is correct |
52 |
Correct |
1997 ms |
81584 KB |
Output is correct |
53 |
Correct |
1132 ms |
80432 KB |
Output is correct |
54 |
Correct |
1038 ms |
80560 KB |
Output is correct |
55 |
Correct |
1126 ms |
79536 KB |
Output is correct |
56 |
Correct |
213 ms |
2052 KB |
Output is correct |
57 |
Correct |
380 ms |
2036 KB |
Output is correct |
58 |
Correct |
558 ms |
3280 KB |
Output is correct |
59 |
Correct |
1762 ms |
77688 KB |
Output is correct |
60 |
Correct |
2866 ms |
77644 KB |
Output is correct |
61 |
Correct |
1613 ms |
75640 KB |
Output is correct |
62 |
Correct |
1219 ms |
72508 KB |
Output is correct |
63 |
Correct |
2767 ms |
78764 KB |
Output is correct |
64 |
Correct |
1797 ms |
77936 KB |
Output is correct |
65 |
Correct |
1735 ms |
77564 KB |
Output is correct |
66 |
Correct |
1893 ms |
77304 KB |
Output is correct |
67 |
Correct |
1900 ms |
82296 KB |
Output is correct |
68 |
Correct |
1442 ms |
91316 KB |
Output is correct |
69 |
Correct |
2624 ms |
100984 KB |
Output is correct |