# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
272799 |
2020-08-18T15:35:06 Z |
rqi |
Seats (IOI18_seats) |
C++14 |
|
3786 ms |
132068 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef pair<ll, int> T;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define all(x) begin(x), end(x)
const ll INF = 1e18;
T ID = mp(INF, 0);
T comb(T a, T b){
if(a.f == b.f) return mp(a.f, a.s+b.s);
return min(a, b);
}
const int SZ = 1048576;
T seg[2*SZ];
ll lazy[2*SZ];
void pull(int ind){
seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}
void push(int ind, int L, int R){
seg[ind].f+=lazy[ind];
if(L < R){
for(int i = 0; i < 2; i++){
lazy[2*ind+i]+=lazy[ind];
}
}
lazy[ind] = 0;
return;
}
void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1){
push(ind, L, R);
if(L > hi || R < lo) return;
if(lo <= L && R <= hi){
lazy[ind] = inc;
push(ind, L, R);
//cout << "UPD " << ind << " " << L << " " << R << " " << seg[ind].f << " " << seg[ind].s << "\n";
return;
}
int M = (L+R)/2;
upd(lo, hi, inc, 2*ind, L, M); upd(lo, hi, inc, 2*ind+1, M+1, R);
pull(ind);
}
T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
push(ind, L, R);
if(L > hi || R < lo) return ID;
if(lo <= L && R <= hi){
//cout << ind << "\n";
return seg[ind];
}
int M = (L+R)/2;
return comb(query(lo, hi, 2*ind, L, M), query(lo, hi, 2*ind+1, M+1, R));
}
const int mx = 1000005;
int H, W;
pi pos[mx];
vector<vi> stu;
vpi rec = vpi{mp(0, 0), mp(0, 1), mp(1, 0), mp(1, 1)};
vpi rec2 = vpi{mp(-1, -1), mp(-1, 0), mp(0, -1), mp(0, 0)};
vector<pair<pi, bool>> fig[8];
ll val[8];
vector<pair<pi, int>> rot;
bool works(int r, int c, pi dif){
r = r+dif.f;
c = c+dif.s;
if(r < 0 || H-1 < r) return 0;
if(c < 0 || W-1 < c) return 0;
return 1;
}
bool mode = 0;
ll csum[mx];
void updSeat(int r, int c, int con, int typ){
bool good = 1;
int lo = 0;
int hi = H*W-1;
for(auto u: fig[con]){
if(!works(r, c, u.f)){
good = 0;
//cout << "NO WORK " << r << " " << c << " " << con << "\n";
break;
}
if(u.s == 1){
lo = max(lo, stu[r+u.f.f][c+u.f.s]);
}
else{
hi = min(hi, stu[r+u.f.f][c+u.f.s]-1);
}
}
if(lo > hi) good = 0;
if(!good) return;
// cout << "updSeat: " << r << " " << c << " " << con << " " << typ << "\n";
// cout << "seg update " << lo << " " << hi << " " << val[con]*typ << "\n";
if(mode == 0){
csum[lo]+=val[con]*typ;
csum[hi+1]-=val[con]*typ;
}
else upd(lo, hi, val[con]*typ);
}
void give_initial_chart(int _H, int _W, vi R, vi C) {
for(int i = 0; i < 5; i++){
for(int k = 0; k < 4; k++){
bool x = 1;
if(i == k) x = 0;
fig[i].pb(mp(rec[k], x));
}
}
for(int i = 5; i < 8; i++){
fig[i].pb(mp(mp(0, 0), 1));
}
fig[6].pb(mp(mp(0, 1), 1));
fig[7].pb(mp(mp(1, 0), 1));
val[0] = val[1] = val[2] = val[3] = 1000000000LL;
val[4] = 1;
val[5] = 1;
val[6] = -1;
val[7] = -1;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 5; j++){
rot.pb(mp(rec2[i], j));
}
}
for(int i = 5; i < 8; i++){
rot.pb(mp(mp(0, 0), i));
}
rot.pb(mp(rec2[2], 6));
rot.pb(mp(rec2[1], 7));
// cout << "rot:\n";
// for(auto u: rot){
// cout << u.f.f << " " << u.f.s << " " << u.s << "\n";
// }
// cout << "\n";
// for(int i = 0; i < 4; i++){
// int r = rec1[i].f;
// int c = rec1[i].s;
// for(int j = 0; j < 4; j++){
// for(int k = 0; k < 4; k++){
// bool x = 1;
// if(j == k) x = 0;
// fig[4*i+j].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), x));
// }
// val[4*i+j] = 1000000000LL;
// }
// }
// for(int i = 0; i < 4; i++){
// int r = rec1[i].f;
// int c = rec1[i].s;
// for(int k = 0; k < 4; k++){
// fig[16+i].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), 1));
// }
// val[16+i] = 1;
// }
// for(int i = 0; i <= 4; i++){
// fig[20+i].pb(mp(mp(0, 0), 1));
// }
// fig[21].pb(mp(mp(0, -1), 1));
// fig[22].pb(mp(mp(0, 1), 1));
// fig[23].pb(mp(mp(-1, 0), 1));
// fig[24].pb(mp(mp(1, 0), 1));
// val[20] = 1;
// val[21] = val[22] = val[23] = val[24] = -1;
for(int i = SZ; i < 2*SZ; i++){
seg[i] = mp(0, 1);
}
// cout << seg[1+SZ].f << " " << seg[1+SZ].s << "\n";
// T q1 = query(1, 1);
// cout << q1.f << " " << q1.s << "\n";
// upd(1, 1, 5);
// q1 = query(1, 1);
// cout << q1.f << " " << q1.s << "\n";
// cout << "////////////////\n";
H = _H;
W = _W;
stu = vector<vi>(H, vi(W, 0));
for(int i = 0; i < H*W; i++){
pos[i] = mp(R[i], C[i]);
stu[R[i]][C[i]] = i;
}
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
for(int k = 0; k < 8; k++){
updSeat(i, j, k, 1);
}
}
}
for(int i = 1; i < H*W; i++){
csum[i]+=csum[i-1];
}
for(int i = 0; i < H*W; i++){
seg[i+SZ] = mp(csum[i], 1);
}
for(int i = SZ-1; i >= 1; i--){
pull(i);
}
mode = 1;
// for(int i = 0; i < H*W; i++){
// T q1 = query(i, i);
// cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
// }
// T q1 = query(0, H*W-1);
// cout << "query " << " " << q1.f << " " << q1.s << "\n";
}
int swap_seats(int a, int b) {
//cout << "swap_seats " << a << " " << b << "\n";
pi pos1 = pos[a];
pi pos2 = pos[b];
vector<pair<pi, int>> upds;
for(auto u: rot){
upds.pb(mp(mp(pos1.f+u.f.f, pos1.s+u.f.s), u.s));
}
for(auto u: rot){
upds.pb(mp(mp(pos2.f+u.f.f, pos2.s+u.f.s), u.s));
}
// for(auto u: upds){
// cout << "upds " << u.f.f << " " << u.f.s << " " << u.s << " " << "\n";
// }
sort(all(upds));
upds.erase(unique(all(upds)), end(upds));
for(auto u: upds){
updSeat(u.f.f, u.f.s, u.s, -1);
}
swap(pos[a], pos[b]);
swap(stu[pos1.f][pos1.s], stu[pos2.f][pos2.s]);
for(auto u: upds){
updSeat(u.f.f, u.f.s, u.s, 1);
}
// for(int i = 0; i < H*W; i++){
// T q1 = query(i, i);
// cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
// }
T q = query(0, H*W-1);
assert(q.f == 1);
return q.s;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
33400 KB |
Output is correct |
2 |
Correct |
159 ms |
33400 KB |
Output is correct |
3 |
Correct |
179 ms |
33400 KB |
Output is correct |
4 |
Correct |
81 ms |
33408 KB |
Output is correct |
5 |
Correct |
86 ms |
33400 KB |
Output is correct |
6 |
Correct |
158 ms |
33400 KB |
Output is correct |
7 |
Correct |
176 ms |
33400 KB |
Output is correct |
8 |
Correct |
178 ms |
33400 KB |
Output is correct |
9 |
Correct |
177 ms |
33412 KB |
Output is correct |
10 |
Correct |
170 ms |
33524 KB |
Output is correct |
11 |
Correct |
143 ms |
33356 KB |
Output is correct |
12 |
Correct |
85 ms |
33400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
33400 KB |
Output is correct |
2 |
Correct |
159 ms |
33400 KB |
Output is correct |
3 |
Correct |
179 ms |
33400 KB |
Output is correct |
4 |
Correct |
81 ms |
33408 KB |
Output is correct |
5 |
Correct |
86 ms |
33400 KB |
Output is correct |
6 |
Correct |
158 ms |
33400 KB |
Output is correct |
7 |
Correct |
176 ms |
33400 KB |
Output is correct |
8 |
Correct |
178 ms |
33400 KB |
Output is correct |
9 |
Correct |
177 ms |
33412 KB |
Output is correct |
10 |
Correct |
170 ms |
33524 KB |
Output is correct |
11 |
Correct |
143 ms |
33356 KB |
Output is correct |
12 |
Correct |
85 ms |
33400 KB |
Output is correct |
13 |
Correct |
261 ms |
34120 KB |
Output is correct |
14 |
Correct |
255 ms |
33912 KB |
Output is correct |
15 |
Correct |
101 ms |
34040 KB |
Output is correct |
16 |
Correct |
98 ms |
34428 KB |
Output is correct |
17 |
Correct |
178 ms |
34044 KB |
Output is correct |
18 |
Correct |
239 ms |
34040 KB |
Output is correct |
19 |
Correct |
253 ms |
34040 KB |
Output is correct |
20 |
Correct |
180 ms |
34168 KB |
Output is correct |
21 |
Correct |
100 ms |
34032 KB |
Output is correct |
22 |
Correct |
95 ms |
34424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
984 ms |
87268 KB |
Output is correct |
2 |
Correct |
925 ms |
81120 KB |
Output is correct |
3 |
Correct |
849 ms |
81264 KB |
Output is correct |
4 |
Correct |
837 ms |
81252 KB |
Output is correct |
5 |
Correct |
830 ms |
81248 KB |
Output is correct |
6 |
Correct |
842 ms |
81208 KB |
Output is correct |
7 |
Correct |
862 ms |
81120 KB |
Output is correct |
8 |
Correct |
897 ms |
81200 KB |
Output is correct |
9 |
Correct |
892 ms |
81124 KB |
Output is correct |
10 |
Correct |
846 ms |
81148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
34008 KB |
Output is correct |
2 |
Correct |
342 ms |
38584 KB |
Output is correct |
3 |
Correct |
869 ms |
79972 KB |
Output is correct |
4 |
Correct |
1022 ms |
81124 KB |
Output is correct |
5 |
Correct |
646 ms |
80548 KB |
Output is correct |
6 |
Correct |
909 ms |
132068 KB |
Output is correct |
7 |
Correct |
853 ms |
81052 KB |
Output is correct |
8 |
Correct |
880 ms |
81120 KB |
Output is correct |
9 |
Correct |
864 ms |
81636 KB |
Output is correct |
10 |
Correct |
832 ms |
84196 KB |
Output is correct |
11 |
Correct |
754 ms |
103980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
449 ms |
35244 KB |
Output is correct |
2 |
Correct |
533 ms |
34932 KB |
Output is correct |
3 |
Correct |
609 ms |
34932 KB |
Output is correct |
4 |
Correct |
639 ms |
35060 KB |
Output is correct |
5 |
Correct |
683 ms |
35560 KB |
Output is correct |
6 |
Correct |
1437 ms |
88384 KB |
Output is correct |
7 |
Correct |
1423 ms |
88368 KB |
Output is correct |
8 |
Correct |
1383 ms |
88284 KB |
Output is correct |
9 |
Correct |
1589 ms |
88272 KB |
Output is correct |
10 |
Correct |
1357 ms |
88336 KB |
Output is correct |
11 |
Correct |
1333 ms |
86440 KB |
Output is correct |
12 |
Correct |
1483 ms |
86432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
33400 KB |
Output is correct |
2 |
Correct |
159 ms |
33400 KB |
Output is correct |
3 |
Correct |
179 ms |
33400 KB |
Output is correct |
4 |
Correct |
81 ms |
33408 KB |
Output is correct |
5 |
Correct |
86 ms |
33400 KB |
Output is correct |
6 |
Correct |
158 ms |
33400 KB |
Output is correct |
7 |
Correct |
176 ms |
33400 KB |
Output is correct |
8 |
Correct |
178 ms |
33400 KB |
Output is correct |
9 |
Correct |
177 ms |
33412 KB |
Output is correct |
10 |
Correct |
170 ms |
33524 KB |
Output is correct |
11 |
Correct |
143 ms |
33356 KB |
Output is correct |
12 |
Correct |
85 ms |
33400 KB |
Output is correct |
13 |
Correct |
261 ms |
34120 KB |
Output is correct |
14 |
Correct |
255 ms |
33912 KB |
Output is correct |
15 |
Correct |
101 ms |
34040 KB |
Output is correct |
16 |
Correct |
98 ms |
34428 KB |
Output is correct |
17 |
Correct |
178 ms |
34044 KB |
Output is correct |
18 |
Correct |
239 ms |
34040 KB |
Output is correct |
19 |
Correct |
253 ms |
34040 KB |
Output is correct |
20 |
Correct |
180 ms |
34168 KB |
Output is correct |
21 |
Correct |
100 ms |
34032 KB |
Output is correct |
22 |
Correct |
95 ms |
34424 KB |
Output is correct |
23 |
Correct |
984 ms |
87268 KB |
Output is correct |
24 |
Correct |
925 ms |
81120 KB |
Output is correct |
25 |
Correct |
849 ms |
81264 KB |
Output is correct |
26 |
Correct |
837 ms |
81252 KB |
Output is correct |
27 |
Correct |
830 ms |
81248 KB |
Output is correct |
28 |
Correct |
842 ms |
81208 KB |
Output is correct |
29 |
Correct |
862 ms |
81120 KB |
Output is correct |
30 |
Correct |
897 ms |
81200 KB |
Output is correct |
31 |
Correct |
892 ms |
81124 KB |
Output is correct |
32 |
Correct |
846 ms |
81148 KB |
Output is correct |
33 |
Correct |
275 ms |
34008 KB |
Output is correct |
34 |
Correct |
342 ms |
38584 KB |
Output is correct |
35 |
Correct |
869 ms |
79972 KB |
Output is correct |
36 |
Correct |
1022 ms |
81124 KB |
Output is correct |
37 |
Correct |
646 ms |
80548 KB |
Output is correct |
38 |
Correct |
909 ms |
132068 KB |
Output is correct |
39 |
Correct |
853 ms |
81052 KB |
Output is correct |
40 |
Correct |
880 ms |
81120 KB |
Output is correct |
41 |
Correct |
864 ms |
81636 KB |
Output is correct |
42 |
Correct |
832 ms |
84196 KB |
Output is correct |
43 |
Correct |
754 ms |
103980 KB |
Output is correct |
44 |
Correct |
449 ms |
35244 KB |
Output is correct |
45 |
Correct |
533 ms |
34932 KB |
Output is correct |
46 |
Correct |
609 ms |
34932 KB |
Output is correct |
47 |
Correct |
639 ms |
35060 KB |
Output is correct |
48 |
Correct |
683 ms |
35560 KB |
Output is correct |
49 |
Correct |
1437 ms |
88384 KB |
Output is correct |
50 |
Correct |
1423 ms |
88368 KB |
Output is correct |
51 |
Correct |
1383 ms |
88284 KB |
Output is correct |
52 |
Correct |
1589 ms |
88272 KB |
Output is correct |
53 |
Correct |
1357 ms |
88336 KB |
Output is correct |
54 |
Correct |
1333 ms |
86440 KB |
Output is correct |
55 |
Correct |
1483 ms |
86432 KB |
Output is correct |
56 |
Correct |
1002 ms |
35232 KB |
Output is correct |
57 |
Correct |
1610 ms |
34924 KB |
Output is correct |
58 |
Correct |
2242 ms |
35544 KB |
Output is correct |
59 |
Correct |
3293 ms |
80676 KB |
Output is correct |
60 |
Correct |
3786 ms |
80632 KB |
Output is correct |
61 |
Correct |
3181 ms |
80612 KB |
Output is correct |
62 |
Correct |
2182 ms |
80452 KB |
Output is correct |
63 |
Correct |
3409 ms |
80148 KB |
Output is correct |
64 |
Correct |
3099 ms |
79248 KB |
Output is correct |
65 |
Correct |
3143 ms |
80472 KB |
Output is correct |
66 |
Correct |
3384 ms |
79960 KB |
Output is correct |
67 |
Correct |
3151 ms |
83524 KB |
Output is correct |
68 |
Correct |
2919 ms |
93704 KB |
Output is correct |
69 |
Correct |
2778 ms |
102792 KB |
Output is correct |