#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1001000;
const int mxM=200100;
const int mxK=61;
const int MOD=1e9;
const ll INF=1e18;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
typedef struct lazyseg{
pii seg[4*mxN]={};
int lazy[4*mxN]={};
pii mrg(pii a, pii b){
if(a.fi!=b.fi) return max(a, b);
return pii(a.fi, a.se+b.se);
}
void init(int idx, int s, int e){
seg[idx]=pii(0, e-s+1);
if(s==e) return;
int mid=(s+e)/2;
init(2*idx, s, mid);
init(2*idx+1, mid+1, e);
}
void propagate(int idx){
seg[2*idx].fi+=lazy[idx];
seg[2*idx+1].fi+=lazy[idx];
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
lazy[idx]=0;
}
void upd(int idx, int s1, int e1, int s2, int e2, int x){
if(s2>e1 || s1>e2) return;
if(s2<=s1 && e1<=e2){
seg[idx].fi+=x, lazy[idx]+=x;
return;
}
propagate(idx);
int mid=(s1+e1)/2;
upd(2*idx, s1, mid, s2, e2, x);
upd(2*idx+1, mid+1, e1, s2, e2, x);
seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
}
}lazyseg;
int H, W, Q;
vector <vector <int>> v;
bool Chk[mxN];
pii pos[mxN];
pii qry[mxN];
lazyseg T1;
void input(){
cin >> H >> W >> Q;
v.resize(H);
for(int i=0;i<H;i++) v[i].resize(W);
for(int i=0;i<H*W;i++){
int a, b;
cin >> a >> b;
v[a][b]=i;
pos[i]=pii(a, b);
}
for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}
bool not_ok(int a, int b){
return (a<0 || a>=H || b<0 || b>=W);
}
void add(int a, int rev){
auto [ax, ay]=pos[a];
for(int i=0;i<4;i++){
int nx1=ax+dx[i], ny1=ay+dy[i], nx2=ax+dx[(i+1)%4], ny2=ay+dy[(i+1)%4];
int val1, val2;
if(not_ok(nx1, ny1)) val1=H*W;
else val1=v[nx1][ny1];
if(not_ok(nx2, ny2)) val2=H*W;
else val2=v[nx2][ny2];
if(a<val1 && a<val2) T1.upd(1, 0, H*W-1, a, min(val1, val2)-1, -rev);
if(a>val1 && a>val2) T1.upd(1, 0, H*W-1, max(val1, val2), a-1, -rev);
}
}
void add_area(int a, bool rev){ //rev가 true면 제거하는 것
int flag=(rev ? -1 : 1);
auto [ax, ay]=pos[a];
if(Chk[a]==rev) Chk[a]=(!rev), add(a, flag);
for(int i=0;i<4;i++){
if(not_ok(ax+dx[i], ay+dy[i])) continue;
int av=v[ax+dx[i]][ay+dy[i]];
if(Chk[av]==rev) Chk[av]=(!rev), add(av, flag);
}
}
void init(){
T1.init(1, 0, H*W-1);
for(int i=0;i<H*W;i++){
add(i, 1);
Chk[i]=true;
}
}
int swap_seats(int a, int b){
add_area(a, true), add_area(b, true);
auto [ax, ay]=pos[a];
auto [bx, by]=pos[b];
swap(v[ax][ay], v[bx][by]);
swap(pos[a], pos[b]);
add_area(a, false), add_area(b, false);
return (T1.seg[1].fi==-4 ? T1.seg[1].se : 0);
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c){
H=h, W=w;
v.resize(H);
for(int i=0;i<H;i++) v[i].resize(W);
for(int i=0;i<H*W;i++){
v[r[i]][c[i]]=i;
pos[i]=pii(r[i], c[i]);
}
init();
}
/*
int main()
{
gibon
input();
init();
for(int i=1;i<=Q;i++) cout << swap_seats(qry[i].fi, qry[i].se) << '\n';
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2648 KB |
Output is correct |
2 |
Correct |
18 ms |
2636 KB |
Output is correct |
3 |
Correct |
32 ms |
2896 KB |
Output is correct |
4 |
Correct |
19 ms |
2652 KB |
Output is correct |
5 |
Correct |
17 ms |
2500 KB |
Output is correct |
6 |
Correct |
27 ms |
2648 KB |
Output is correct |
7 |
Correct |
28 ms |
2648 KB |
Output is correct |
8 |
Correct |
25 ms |
2652 KB |
Output is correct |
9 |
Correct |
25 ms |
2656 KB |
Output is correct |
10 |
Correct |
28 ms |
2640 KB |
Output is correct |
11 |
Correct |
26 ms |
2648 KB |
Output is correct |
12 |
Correct |
16 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2648 KB |
Output is correct |
2 |
Correct |
18 ms |
2636 KB |
Output is correct |
3 |
Correct |
32 ms |
2896 KB |
Output is correct |
4 |
Correct |
19 ms |
2652 KB |
Output is correct |
5 |
Correct |
17 ms |
2500 KB |
Output is correct |
6 |
Correct |
27 ms |
2648 KB |
Output is correct |
7 |
Correct |
28 ms |
2648 KB |
Output is correct |
8 |
Correct |
25 ms |
2652 KB |
Output is correct |
9 |
Correct |
25 ms |
2656 KB |
Output is correct |
10 |
Correct |
28 ms |
2640 KB |
Output is correct |
11 |
Correct |
26 ms |
2648 KB |
Output is correct |
12 |
Correct |
16 ms |
2652 KB |
Output is correct |
13 |
Correct |
70 ms |
5464 KB |
Output is correct |
14 |
Correct |
84 ms |
5208 KB |
Output is correct |
15 |
Correct |
43 ms |
5212 KB |
Output is correct |
16 |
Correct |
33 ms |
5720 KB |
Output is correct |
17 |
Correct |
56 ms |
5212 KB |
Output is correct |
18 |
Correct |
58 ms |
5212 KB |
Output is correct |
19 |
Correct |
50 ms |
5412 KB |
Output is correct |
20 |
Correct |
43 ms |
5468 KB |
Output is correct |
21 |
Correct |
33 ms |
5208 KB |
Output is correct |
22 |
Correct |
33 ms |
5724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1836 ms |
72540 KB |
Output is correct |
2 |
Correct |
789 ms |
72784 KB |
Output is correct |
3 |
Correct |
709 ms |
72904 KB |
Output is correct |
4 |
Correct |
732 ms |
73040 KB |
Output is correct |
5 |
Correct |
762 ms |
72536 KB |
Output is correct |
6 |
Correct |
700 ms |
72540 KB |
Output is correct |
7 |
Correct |
703 ms |
72640 KB |
Output is correct |
8 |
Correct |
723 ms |
72628 KB |
Output is correct |
9 |
Correct |
732 ms |
72652 KB |
Output is correct |
10 |
Correct |
741 ms |
72480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
5268 KB |
Output is correct |
2 |
Correct |
125 ms |
8784 KB |
Output is correct |
3 |
Correct |
726 ms |
72624 KB |
Output is correct |
4 |
Correct |
1773 ms |
72512 KB |
Output is correct |
5 |
Correct |
674 ms |
72528 KB |
Output is correct |
6 |
Correct |
1528 ms |
123268 KB |
Output is correct |
7 |
Correct |
738 ms |
72640 KB |
Output is correct |
8 |
Correct |
795 ms |
72604 KB |
Output is correct |
9 |
Correct |
705 ms |
72768 KB |
Output is correct |
10 |
Correct |
769 ms |
75572 KB |
Output is correct |
11 |
Correct |
743 ms |
96020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
4048 KB |
Output is correct |
2 |
Correct |
85 ms |
4436 KB |
Output is correct |
3 |
Correct |
149 ms |
4160 KB |
Output is correct |
4 |
Correct |
212 ms |
4152 KB |
Output is correct |
5 |
Correct |
364 ms |
6732 KB |
Output is correct |
6 |
Correct |
1106 ms |
73556 KB |
Output is correct |
7 |
Correct |
1222 ms |
73560 KB |
Output is correct |
8 |
Correct |
1071 ms |
73384 KB |
Output is correct |
9 |
Correct |
1768 ms |
73460 KB |
Output is correct |
10 |
Correct |
1034 ms |
73536 KB |
Output is correct |
11 |
Correct |
1054 ms |
73400 KB |
Output is correct |
12 |
Correct |
1018 ms |
73556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2648 KB |
Output is correct |
2 |
Correct |
18 ms |
2636 KB |
Output is correct |
3 |
Correct |
32 ms |
2896 KB |
Output is correct |
4 |
Correct |
19 ms |
2652 KB |
Output is correct |
5 |
Correct |
17 ms |
2500 KB |
Output is correct |
6 |
Correct |
27 ms |
2648 KB |
Output is correct |
7 |
Correct |
28 ms |
2648 KB |
Output is correct |
8 |
Correct |
25 ms |
2652 KB |
Output is correct |
9 |
Correct |
25 ms |
2656 KB |
Output is correct |
10 |
Correct |
28 ms |
2640 KB |
Output is correct |
11 |
Correct |
26 ms |
2648 KB |
Output is correct |
12 |
Correct |
16 ms |
2652 KB |
Output is correct |
13 |
Correct |
70 ms |
5464 KB |
Output is correct |
14 |
Correct |
84 ms |
5208 KB |
Output is correct |
15 |
Correct |
43 ms |
5212 KB |
Output is correct |
16 |
Correct |
33 ms |
5720 KB |
Output is correct |
17 |
Correct |
56 ms |
5212 KB |
Output is correct |
18 |
Correct |
58 ms |
5212 KB |
Output is correct |
19 |
Correct |
50 ms |
5412 KB |
Output is correct |
20 |
Correct |
43 ms |
5468 KB |
Output is correct |
21 |
Correct |
33 ms |
5208 KB |
Output is correct |
22 |
Correct |
33 ms |
5724 KB |
Output is correct |
23 |
Correct |
1836 ms |
72540 KB |
Output is correct |
24 |
Correct |
789 ms |
72784 KB |
Output is correct |
25 |
Correct |
709 ms |
72904 KB |
Output is correct |
26 |
Correct |
732 ms |
73040 KB |
Output is correct |
27 |
Correct |
762 ms |
72536 KB |
Output is correct |
28 |
Correct |
700 ms |
72540 KB |
Output is correct |
29 |
Correct |
703 ms |
72640 KB |
Output is correct |
30 |
Correct |
723 ms |
72628 KB |
Output is correct |
31 |
Correct |
732 ms |
72652 KB |
Output is correct |
32 |
Correct |
741 ms |
72480 KB |
Output is correct |
33 |
Correct |
65 ms |
5268 KB |
Output is correct |
34 |
Correct |
125 ms |
8784 KB |
Output is correct |
35 |
Correct |
726 ms |
72624 KB |
Output is correct |
36 |
Correct |
1773 ms |
72512 KB |
Output is correct |
37 |
Correct |
674 ms |
72528 KB |
Output is correct |
38 |
Correct |
1528 ms |
123268 KB |
Output is correct |
39 |
Correct |
738 ms |
72640 KB |
Output is correct |
40 |
Correct |
795 ms |
72604 KB |
Output is correct |
41 |
Correct |
705 ms |
72768 KB |
Output is correct |
42 |
Correct |
769 ms |
75572 KB |
Output is correct |
43 |
Correct |
743 ms |
96020 KB |
Output is correct |
44 |
Correct |
28 ms |
4048 KB |
Output is correct |
45 |
Correct |
85 ms |
4436 KB |
Output is correct |
46 |
Correct |
149 ms |
4160 KB |
Output is correct |
47 |
Correct |
212 ms |
4152 KB |
Output is correct |
48 |
Correct |
364 ms |
6732 KB |
Output is correct |
49 |
Correct |
1106 ms |
73556 KB |
Output is correct |
50 |
Correct |
1222 ms |
73560 KB |
Output is correct |
51 |
Correct |
1071 ms |
73384 KB |
Output is correct |
52 |
Correct |
1768 ms |
73460 KB |
Output is correct |
53 |
Correct |
1034 ms |
73536 KB |
Output is correct |
54 |
Correct |
1054 ms |
73400 KB |
Output is correct |
55 |
Correct |
1018 ms |
73556 KB |
Output is correct |
56 |
Correct |
109 ms |
4136 KB |
Output is correct |
57 |
Correct |
312 ms |
4136 KB |
Output is correct |
58 |
Correct |
484 ms |
6780 KB |
Output is correct |
59 |
Correct |
1505 ms |
73388 KB |
Output is correct |
60 |
Correct |
3027 ms |
73780 KB |
Output is correct |
61 |
Correct |
1372 ms |
73644 KB |
Output is correct |
62 |
Correct |
1167 ms |
73404 KB |
Output is correct |
63 |
Correct |
2662 ms |
73928 KB |
Output is correct |
64 |
Correct |
1631 ms |
73512 KB |
Output is correct |
65 |
Correct |
1347 ms |
73532 KB |
Output is correct |
66 |
Correct |
1489 ms |
74104 KB |
Output is correct |
67 |
Correct |
1595 ms |
76876 KB |
Output is correct |
68 |
Correct |
1303 ms |
87744 KB |
Output is correct |
69 |
Correct |
2815 ms |
96952 KB |
Output is correct |