#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
int val1,val2,cnt,lazy1,lazy2;
node(){
val1 = 0,val2 = 0,cnt = 1,lazy1 = 0,lazy2 = 0;
}
node(int a){
val1 = 1e9,val2 = 1e9,cnt = 0,lazy1 = 0,lazy2 = 0;
}
};
node merge(node a,node b){
node ret(-1);
ret.val1 = min(a.val1,b.val1);
if(a.val1 == ret.val1)
ret.val2 = min(ret.val2,a.val2);
if(b.val1 == ret.val1)
ret.val2 = min(ret.val2,b.val2);
if(a.val1 == ret.val1 && a.val2 == ret.val2){
ret.cnt += a.cnt;
}
if(b.val1 == ret.val1 && b.val2 == ret.val2){
ret.cnt += b.cnt;
}
return ret;
}
int val1[N],val2[N];
struct SegTree{
vector<node> t;
int n;
void init(int size){
n = size;
t.assign(4*n,node());
}
void build(int v,int tl,int tr){
if(tl == tr){
t[v].val1 = val1[tl];
t[v].val2 = val2[tl];
t[v].cnt = 1;
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v] = merge(t[v*2],t[v*2+1]);
}
void push(int v){
t[v*2].val1 += t[v].lazy1;
t[v*2].val2 += t[v].lazy2;
t[v*2].lazy1 += t[v].lazy1;
t[v*2].lazy2 += t[v].lazy2;
t[v*2+1].val1 += t[v].lazy1;
t[v*2+1].val2 += t[v].lazy2;
t[v*2+1].lazy1 += t[v].lazy1;
t[v*2+1].lazy2 += t[v].lazy2;
t[v].lazy1 = t[v].lazy2 = 0;
}
void upd(int v,int tl,int tr,int l,int r,pair<int,int> val){
if(tr < l || r < tl)
return;
if(l <= tl && tr <= r){
t[v].val1 += val.first;
t[v].val2 += val.second;
t[v].lazy1 += val.first;
t[v].lazy2 += val.second;
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return node(-1);
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int l,int r,pair<int,int> val){
if(l > r)return;
upd(1,1,n,l,r,val);
}
void upd(pair<int,int> range,pair<int,int> val){
upd(range.first,range.second,val);
}
node get(int l,int r){
if(l > r)return node(-1);
return get(1,1,n,l,r);
}
};
SegTree tree;
vector<vector<int>> grid;
int n;
vector<int> r,c;
pair<int,int> getw(pair<int,int> a){
return {1,grid[a.first][a.second] - 1};
}
pair<int,int> getb(pair<int,int> a){
return {grid[a.first][a.second], n};
}
pair<int,int> intersect(pair<int,int> a,pair<int,int> b){
return {max(a.first,b.first),min(a.second,b.second)};
}
vector<pair<int,int>> rect(int x,int y){
vector<pair<int,int>> ret;
for(int i = 0;i<=1;i++){
for(int j = 0;j<=1;j++){
ret.push_back({x+i,y+j});
}
}
return ret;
}
void init1(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getb(points[j]));
}
else range = intersect(range,getw(points[j]));
}
if(range.first > range.second)continue;
val1[range.first] += coef;
val1[range.second + 1] -= coef;
}
}
void init2(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getw(points[j]));
}
else range = intersect(range,getb(points[j]));
}
if(range.first > range.second)continue;
val2[range.first] += coef;
val2[range.second + 1] -= coef;
}
}
void upd1(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getb(points[j]));
}
else range = intersect(range,getw(points[j]));
}
tree.upd(range,{coef,0});
}
}
void upd2(vector<pair<int,int>> points,int coef){
for(int i = 0;i<points.size();i++){
pair<int,int> range = {-1e9,1e9};
for(int j = 0;j<points.size();j++){
if(i == j){
range = intersect(range,getw(points[j]));
}
else range = intersect(range,getb(points[j]));
}
tree.upd(range,{0,coef});
}
}
void upd(int x,int y,int coef){
pair<int,int> range;
vector<pair<int,int>> points;
//*.
//..
//xa
//aa
points = rect(x-1,y-1);
upd1(points,coef);
//ax
//aa
points = rect(x-1,y);
upd1(points,coef);
//aa
//xa
points = rect(x,y-1);
upd1(points,coef);
//aa
//ax
points = rect(x,y);
upd1(points,coef);
//.*
//**
//xa
//aa
points = rect(x-1,y-1);
upd2(points,coef);
//ax
//aa
points = rect(x-1,y);
upd2(points,coef);
//aa
//xa
points = rect(x,y-1);
upd2(points,coef);
//aa
//ax
points = rect(x,y);
upd2(points,coef);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
r = R;
c = C;
grid = vector<vector<int>> (H+2,vector<int>(W+2,H*W+1));
tree.init(n);
for(int i = 0;i<n;i++){
r[i]++;
c[i]++;
grid[r[i]][c[i]] = i+1;
// upd(r[i],c[i],1);
// for(int j = 1;j<=n;j++){
// cout << tree.get(j,j).val1 << " " << tree.get(j,j).val2 << " " << tree.get(j,j).cnt << endl;
// }
// cout << endl;
}
for(int i = 0;i<=H;i++){
for(int j = 0;j<=W;j++){
init1(rect(i,j),1);
init2(rect(i,j),1);
}
}
for(int i = 1;i<=n;i++){
val1[i] += val1[i-1];
val2[i] += val2[i-1];
}
tree.build(1,1,n);
// for(int i = 1;i<=n;i++){
// cout << tree.get(i,i).val1 << " " << tree.get(i,i).val2 << " " << tree.get(i,i).cnt << endl;
// }
}
int swap_seats(int a, int b) {
upd(r[a],c[a],-1);
upd(r[b],c[b],-1);
swap(grid[r[a]][c[a]],grid[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
upd(r[a],c[a],1);
upd(r[b],c[b],1);
return tree.get(1,n).cnt;
}
Compilation message
seats.cpp: In function 'void init1(std::vector<std::pair<int, int> >, int)':
seats.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int i = 0;i<points.size();i++){
| ~^~~~~~~~~~~~~~
seats.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int j = 0;j<points.size();j++){
| ~^~~~~~~~~~~~~~
seats.cpp: In function 'void init2(std::vector<std::pair<int, int> >, int)':
seats.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i = 0;i<points.size();i++){
| ~^~~~~~~~~~~~~~
seats.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int j = 0;j<points.size();j++){
| ~^~~~~~~~~~~~~~
seats.cpp: In function 'void upd1(std::vector<std::pair<int, int> >, int)':
seats.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int i = 0;i<points.size();i++){
| ~^~~~~~~~~~~~~~
seats.cpp:154:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int j = 0;j<points.size();j++){
| ~^~~~~~~~~~~~~~
seats.cpp: In function 'void upd2(std::vector<std::pair<int, int> >, int)':
seats.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int i = 0;i<points.size();i++){
| ~^~~~~~~~~~~~~~
seats.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int j = 0;j<points.size();j++){
| ~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
416 KB |
Output is correct |
2 |
Correct |
50 ms |
424 KB |
Output is correct |
3 |
Correct |
68 ms |
436 KB |
Output is correct |
4 |
Correct |
48 ms |
460 KB |
Output is correct |
5 |
Correct |
45 ms |
436 KB |
Output is correct |
6 |
Correct |
61 ms |
436 KB |
Output is correct |
7 |
Correct |
64 ms |
436 KB |
Output is correct |
8 |
Correct |
64 ms |
436 KB |
Output is correct |
9 |
Correct |
59 ms |
436 KB |
Output is correct |
10 |
Correct |
71 ms |
460 KB |
Output is correct |
11 |
Correct |
62 ms |
552 KB |
Output is correct |
12 |
Correct |
45 ms |
448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
416 KB |
Output is correct |
2 |
Correct |
50 ms |
424 KB |
Output is correct |
3 |
Correct |
68 ms |
436 KB |
Output is correct |
4 |
Correct |
48 ms |
460 KB |
Output is correct |
5 |
Correct |
45 ms |
436 KB |
Output is correct |
6 |
Correct |
61 ms |
436 KB |
Output is correct |
7 |
Correct |
64 ms |
436 KB |
Output is correct |
8 |
Correct |
64 ms |
436 KB |
Output is correct |
9 |
Correct |
59 ms |
436 KB |
Output is correct |
10 |
Correct |
71 ms |
460 KB |
Output is correct |
11 |
Correct |
62 ms |
552 KB |
Output is correct |
12 |
Correct |
45 ms |
448 KB |
Output is correct |
13 |
Correct |
140 ms |
1664 KB |
Output is correct |
14 |
Correct |
136 ms |
1668 KB |
Output is correct |
15 |
Correct |
83 ms |
1776 KB |
Output is correct |
16 |
Correct |
78 ms |
2252 KB |
Output is correct |
17 |
Correct |
104 ms |
1724 KB |
Output is correct |
18 |
Correct |
109 ms |
1676 KB |
Output is correct |
19 |
Correct |
101 ms |
1716 KB |
Output is correct |
20 |
Correct |
89 ms |
1912 KB |
Output is correct |
21 |
Correct |
74 ms |
1788 KB |
Output is correct |
22 |
Correct |
85 ms |
2132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
895 ms |
116184 KB |
Output is correct |
2 |
Correct |
690 ms |
114304 KB |
Output is correct |
3 |
Correct |
709 ms |
114400 KB |
Output is correct |
4 |
Correct |
669 ms |
114408 KB |
Output is correct |
5 |
Correct |
653 ms |
114476 KB |
Output is correct |
6 |
Correct |
651 ms |
114504 KB |
Output is correct |
7 |
Correct |
654 ms |
114324 KB |
Output is correct |
8 |
Correct |
650 ms |
114412 KB |
Output is correct |
9 |
Correct |
662 ms |
114408 KB |
Output is correct |
10 |
Correct |
778 ms |
114508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
130 ms |
1692 KB |
Output is correct |
2 |
Correct |
200 ms |
11140 KB |
Output is correct |
3 |
Correct |
662 ms |
115432 KB |
Output is correct |
4 |
Correct |
887 ms |
115048 KB |
Output is correct |
5 |
Correct |
894 ms |
122836 KB |
Output is correct |
6 |
Correct |
1288 ms |
165180 KB |
Output is correct |
7 |
Correct |
722 ms |
117072 KB |
Output is correct |
8 |
Correct |
670 ms |
114368 KB |
Output is correct |
9 |
Correct |
714 ms |
114636 KB |
Output is correct |
10 |
Correct |
693 ms |
118988 KB |
Output is correct |
11 |
Correct |
802 ms |
137724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
274 ms |
1996 KB |
Output is correct |
2 |
Correct |
357 ms |
2068 KB |
Output is correct |
3 |
Correct |
430 ms |
2008 KB |
Output is correct |
4 |
Correct |
566 ms |
2096 KB |
Output is correct |
5 |
Correct |
775 ms |
3112 KB |
Output is correct |
6 |
Correct |
1773 ms |
124052 KB |
Output is correct |
7 |
Correct |
1820 ms |
125268 KB |
Output is correct |
8 |
Correct |
1832 ms |
125272 KB |
Output is correct |
9 |
Correct |
2077 ms |
125276 KB |
Output is correct |
10 |
Correct |
1892 ms |
138528 KB |
Output is correct |
11 |
Correct |
1860 ms |
138596 KB |
Output is correct |
12 |
Correct |
1888 ms |
138528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
416 KB |
Output is correct |
2 |
Correct |
50 ms |
424 KB |
Output is correct |
3 |
Correct |
68 ms |
436 KB |
Output is correct |
4 |
Correct |
48 ms |
460 KB |
Output is correct |
5 |
Correct |
45 ms |
436 KB |
Output is correct |
6 |
Correct |
61 ms |
436 KB |
Output is correct |
7 |
Correct |
64 ms |
436 KB |
Output is correct |
8 |
Correct |
64 ms |
436 KB |
Output is correct |
9 |
Correct |
59 ms |
436 KB |
Output is correct |
10 |
Correct |
71 ms |
460 KB |
Output is correct |
11 |
Correct |
62 ms |
552 KB |
Output is correct |
12 |
Correct |
45 ms |
448 KB |
Output is correct |
13 |
Correct |
140 ms |
1664 KB |
Output is correct |
14 |
Correct |
136 ms |
1668 KB |
Output is correct |
15 |
Correct |
83 ms |
1776 KB |
Output is correct |
16 |
Correct |
78 ms |
2252 KB |
Output is correct |
17 |
Correct |
104 ms |
1724 KB |
Output is correct |
18 |
Correct |
109 ms |
1676 KB |
Output is correct |
19 |
Correct |
101 ms |
1716 KB |
Output is correct |
20 |
Correct |
89 ms |
1912 KB |
Output is correct |
21 |
Correct |
74 ms |
1788 KB |
Output is correct |
22 |
Correct |
85 ms |
2132 KB |
Output is correct |
23 |
Correct |
895 ms |
116184 KB |
Output is correct |
24 |
Correct |
690 ms |
114304 KB |
Output is correct |
25 |
Correct |
709 ms |
114400 KB |
Output is correct |
26 |
Correct |
669 ms |
114408 KB |
Output is correct |
27 |
Correct |
653 ms |
114476 KB |
Output is correct |
28 |
Correct |
651 ms |
114504 KB |
Output is correct |
29 |
Correct |
654 ms |
114324 KB |
Output is correct |
30 |
Correct |
650 ms |
114412 KB |
Output is correct |
31 |
Correct |
662 ms |
114408 KB |
Output is correct |
32 |
Correct |
778 ms |
114508 KB |
Output is correct |
33 |
Correct |
130 ms |
1692 KB |
Output is correct |
34 |
Correct |
200 ms |
11140 KB |
Output is correct |
35 |
Correct |
662 ms |
115432 KB |
Output is correct |
36 |
Correct |
887 ms |
115048 KB |
Output is correct |
37 |
Correct |
894 ms |
122836 KB |
Output is correct |
38 |
Correct |
1288 ms |
165180 KB |
Output is correct |
39 |
Correct |
722 ms |
117072 KB |
Output is correct |
40 |
Correct |
670 ms |
114368 KB |
Output is correct |
41 |
Correct |
714 ms |
114636 KB |
Output is correct |
42 |
Correct |
693 ms |
118988 KB |
Output is correct |
43 |
Correct |
802 ms |
137724 KB |
Output is correct |
44 |
Correct |
274 ms |
1996 KB |
Output is correct |
45 |
Correct |
357 ms |
2068 KB |
Output is correct |
46 |
Correct |
430 ms |
2008 KB |
Output is correct |
47 |
Correct |
566 ms |
2096 KB |
Output is correct |
48 |
Correct |
775 ms |
3112 KB |
Output is correct |
49 |
Correct |
1773 ms |
124052 KB |
Output is correct |
50 |
Correct |
1820 ms |
125268 KB |
Output is correct |
51 |
Correct |
1832 ms |
125272 KB |
Output is correct |
52 |
Correct |
2077 ms |
125276 KB |
Output is correct |
53 |
Correct |
1892 ms |
138528 KB |
Output is correct |
54 |
Correct |
1860 ms |
138596 KB |
Output is correct |
55 |
Correct |
1888 ms |
138528 KB |
Output is correct |
56 |
Correct |
417 ms |
2024 KB |
Output is correct |
57 |
Correct |
730 ms |
2012 KB |
Output is correct |
58 |
Correct |
1179 ms |
3204 KB |
Output is correct |
59 |
Correct |
2254 ms |
130732 KB |
Output is correct |
60 |
Correct |
3207 ms |
130756 KB |
Output is correct |
61 |
Correct |
2338 ms |
130752 KB |
Output is correct |
62 |
Correct |
1954 ms |
134568 KB |
Output is correct |
63 |
Correct |
3280 ms |
133408 KB |
Output is correct |
64 |
Correct |
2391 ms |
131496 KB |
Output is correct |
65 |
Correct |
2419 ms |
130784 KB |
Output is correct |
66 |
Correct |
2342 ms |
131136 KB |
Output is correct |
67 |
Correct |
2496 ms |
135468 KB |
Output is correct |
68 |
Correct |
2083 ms |
145132 KB |
Output is correct |
69 |
Correct |
2643 ms |
154196 KB |
Output is correct |