#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
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];
set<pair<pi, int>> upds;
for(auto u: rot){
upds.ins(mp(mp(pos1.f+u.f.f, pos1.s+u.f.s), u.s));
}
for(auto u: rot){
upds.ins(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";
// }
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
33400 KB |
Output is correct |
2 |
Correct |
182 ms |
33400 KB |
Output is correct |
3 |
Correct |
210 ms |
33516 KB |
Output is correct |
4 |
Correct |
106 ms |
33408 KB |
Output is correct |
5 |
Correct |
102 ms |
33436 KB |
Output is correct |
6 |
Correct |
170 ms |
33400 KB |
Output is correct |
7 |
Correct |
190 ms |
33400 KB |
Output is correct |
8 |
Correct |
187 ms |
33472 KB |
Output is correct |
9 |
Correct |
192 ms |
33400 KB |
Output is correct |
10 |
Correct |
232 ms |
33388 KB |
Output is correct |
11 |
Correct |
173 ms |
33400 KB |
Output is correct |
12 |
Correct |
104 ms |
33432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
33400 KB |
Output is correct |
2 |
Correct |
182 ms |
33400 KB |
Output is correct |
3 |
Correct |
210 ms |
33516 KB |
Output is correct |
4 |
Correct |
106 ms |
33408 KB |
Output is correct |
5 |
Correct |
102 ms |
33436 KB |
Output is correct |
6 |
Correct |
170 ms |
33400 KB |
Output is correct |
7 |
Correct |
190 ms |
33400 KB |
Output is correct |
8 |
Correct |
187 ms |
33472 KB |
Output is correct |
9 |
Correct |
192 ms |
33400 KB |
Output is correct |
10 |
Correct |
232 ms |
33388 KB |
Output is correct |
11 |
Correct |
173 ms |
33400 KB |
Output is correct |
12 |
Correct |
104 ms |
33432 KB |
Output is correct |
13 |
Correct |
288 ms |
33996 KB |
Output is correct |
14 |
Correct |
290 ms |
34040 KB |
Output is correct |
15 |
Correct |
125 ms |
34040 KB |
Output is correct |
16 |
Correct |
113 ms |
34516 KB |
Output is correct |
17 |
Correct |
201 ms |
34040 KB |
Output is correct |
18 |
Correct |
267 ms |
33912 KB |
Output is correct |
19 |
Correct |
268 ms |
34040 KB |
Output is correct |
20 |
Correct |
208 ms |
34220 KB |
Output is correct |
21 |
Correct |
113 ms |
34040 KB |
Output is correct |
22 |
Correct |
112 ms |
34512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1169 ms |
78048 KB |
Output is correct |
2 |
Correct |
946 ms |
92460 KB |
Output is correct |
3 |
Correct |
963 ms |
92424 KB |
Output is correct |
4 |
Correct |
889 ms |
92384 KB |
Output is correct |
5 |
Correct |
930 ms |
92364 KB |
Output is correct |
6 |
Correct |
893 ms |
92436 KB |
Output is correct |
7 |
Correct |
891 ms |
92516 KB |
Output is correct |
8 |
Correct |
895 ms |
92516 KB |
Output is correct |
9 |
Correct |
932 ms |
92388 KB |
Output is correct |
10 |
Correct |
899 ms |
92256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
299 ms |
34008 KB |
Output is correct |
2 |
Correct |
374 ms |
38504 KB |
Output is correct |
3 |
Correct |
889 ms |
77204 KB |
Output is correct |
4 |
Correct |
1066 ms |
92476 KB |
Output is correct |
5 |
Correct |
782 ms |
91676 KB |
Output is correct |
6 |
Correct |
957 ms |
143260 KB |
Output is correct |
7 |
Correct |
840 ms |
92488 KB |
Output is correct |
8 |
Correct |
906 ms |
92416 KB |
Output is correct |
9 |
Correct |
920 ms |
93100 KB |
Output is correct |
10 |
Correct |
884 ms |
95496 KB |
Output is correct |
11 |
Correct |
788 ms |
115300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
566 ms |
34932 KB |
Output is correct |
2 |
Correct |
669 ms |
34932 KB |
Output is correct |
3 |
Correct |
760 ms |
34932 KB |
Output is correct |
4 |
Correct |
765 ms |
35128 KB |
Output is correct |
5 |
Correct |
827 ms |
35952 KB |
Output is correct |
6 |
Correct |
1505 ms |
79176 KB |
Output is correct |
7 |
Correct |
1692 ms |
79112 KB |
Output is correct |
8 |
Correct |
1603 ms |
79048 KB |
Output is correct |
9 |
Correct |
1676 ms |
79276 KB |
Output is correct |
10 |
Correct |
1544 ms |
79044 KB |
Output is correct |
11 |
Correct |
1580 ms |
79020 KB |
Output is correct |
12 |
Correct |
1526 ms |
79064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
33400 KB |
Output is correct |
2 |
Correct |
182 ms |
33400 KB |
Output is correct |
3 |
Correct |
210 ms |
33516 KB |
Output is correct |
4 |
Correct |
106 ms |
33408 KB |
Output is correct |
5 |
Correct |
102 ms |
33436 KB |
Output is correct |
6 |
Correct |
170 ms |
33400 KB |
Output is correct |
7 |
Correct |
190 ms |
33400 KB |
Output is correct |
8 |
Correct |
187 ms |
33472 KB |
Output is correct |
9 |
Correct |
192 ms |
33400 KB |
Output is correct |
10 |
Correct |
232 ms |
33388 KB |
Output is correct |
11 |
Correct |
173 ms |
33400 KB |
Output is correct |
12 |
Correct |
104 ms |
33432 KB |
Output is correct |
13 |
Correct |
288 ms |
33996 KB |
Output is correct |
14 |
Correct |
290 ms |
34040 KB |
Output is correct |
15 |
Correct |
125 ms |
34040 KB |
Output is correct |
16 |
Correct |
113 ms |
34516 KB |
Output is correct |
17 |
Correct |
201 ms |
34040 KB |
Output is correct |
18 |
Correct |
267 ms |
33912 KB |
Output is correct |
19 |
Correct |
268 ms |
34040 KB |
Output is correct |
20 |
Correct |
208 ms |
34220 KB |
Output is correct |
21 |
Correct |
113 ms |
34040 KB |
Output is correct |
22 |
Correct |
112 ms |
34512 KB |
Output is correct |
23 |
Correct |
1169 ms |
78048 KB |
Output is correct |
24 |
Correct |
946 ms |
92460 KB |
Output is correct |
25 |
Correct |
963 ms |
92424 KB |
Output is correct |
26 |
Correct |
889 ms |
92384 KB |
Output is correct |
27 |
Correct |
930 ms |
92364 KB |
Output is correct |
28 |
Correct |
893 ms |
92436 KB |
Output is correct |
29 |
Correct |
891 ms |
92516 KB |
Output is correct |
30 |
Correct |
895 ms |
92516 KB |
Output is correct |
31 |
Correct |
932 ms |
92388 KB |
Output is correct |
32 |
Correct |
899 ms |
92256 KB |
Output is correct |
33 |
Correct |
299 ms |
34008 KB |
Output is correct |
34 |
Correct |
374 ms |
38504 KB |
Output is correct |
35 |
Correct |
889 ms |
77204 KB |
Output is correct |
36 |
Correct |
1066 ms |
92476 KB |
Output is correct |
37 |
Correct |
782 ms |
91676 KB |
Output is correct |
38 |
Correct |
957 ms |
143260 KB |
Output is correct |
39 |
Correct |
840 ms |
92488 KB |
Output is correct |
40 |
Correct |
906 ms |
92416 KB |
Output is correct |
41 |
Correct |
920 ms |
93100 KB |
Output is correct |
42 |
Correct |
884 ms |
95496 KB |
Output is correct |
43 |
Correct |
788 ms |
115300 KB |
Output is correct |
44 |
Correct |
566 ms |
34932 KB |
Output is correct |
45 |
Correct |
669 ms |
34932 KB |
Output is correct |
46 |
Correct |
760 ms |
34932 KB |
Output is correct |
47 |
Correct |
765 ms |
35128 KB |
Output is correct |
48 |
Correct |
827 ms |
35952 KB |
Output is correct |
49 |
Correct |
1505 ms |
79176 KB |
Output is correct |
50 |
Correct |
1692 ms |
79112 KB |
Output is correct |
51 |
Correct |
1603 ms |
79048 KB |
Output is correct |
52 |
Correct |
1676 ms |
79276 KB |
Output is correct |
53 |
Correct |
1544 ms |
79044 KB |
Output is correct |
54 |
Correct |
1580 ms |
79020 KB |
Output is correct |
55 |
Correct |
1526 ms |
79064 KB |
Output is correct |
56 |
Correct |
1244 ms |
35096 KB |
Output is correct |
57 |
Correct |
1927 ms |
34932 KB |
Output is correct |
58 |
Correct |
2386 ms |
35764 KB |
Output is correct |
59 |
Correct |
3484 ms |
94192 KB |
Output is correct |
60 |
Correct |
3869 ms |
94048 KB |
Output is correct |
61 |
Correct |
3342 ms |
94032 KB |
Output is correct |
62 |
Correct |
2456 ms |
94108 KB |
Output is correct |
63 |
Correct |
3499 ms |
94464 KB |
Output is correct |
64 |
Correct |
3210 ms |
94272 KB |
Output is correct |
65 |
Correct |
3382 ms |
94340 KB |
Output is correct |
66 |
Correct |
3438 ms |
94436 KB |
Output is correct |
67 |
Correct |
3292 ms |
97124 KB |
Output is correct |
68 |
Correct |
2969 ms |
108440 KB |
Output is correct |
69 |
Correct |
2880 ms |
117628 KB |
Output is correct |