#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int N=1<<20;
int lst[N], dodaj[2*N], dx[]={1, 0, -1, 0, 0}, dy[]={0, 1, 0, -1, 0}, MA;
pair<int,int>tr[2*N], gdzie[N];
vector<vector<int>>T;
void licz(int v) {
if(tr[2*v].st<tr[2*v+1].st) tr[v]=tr[2*v];
else if(tr[2*v].st>tr[2*v+1].st) tr[v]=tr[2*v+1];
else tr[v]={tr[2*v].st, tr[2*v].nd+tr[2*v+1].nd};
}
void spl(int v) {
tr[2*v].st+=dodaj[v];
tr[2*v+1].st+=dodaj[v];
dodaj[2*v]+=dodaj[v];
dodaj[2*v+1]+=dodaj[v];
dodaj[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(b<l || a>r) return;
if(a<=l && r<=b) {
tr[v].st+=x;
dodaj[v]+=x;
return;
}
if(dodaj[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
licz(v);
}
void cnt(int x, int y, int k) {
if(T[x][y]==MA) return;
if(lst[T[x][y]]==k) return;
lst[T[x][y]]=k;
rep(i, 4) {
int a=min(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]])-1;
int b=max(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]]);
if(T[x][y]<=a) upd(1, 0, N-1, T[x][y], a, k);
if(b<T[x][y]) upd(1, 0, N-1, b, T[x][y]-1, 10*k);
}
}
void give_initial_chart(int H, int W, vector<int>R, vector<int>C) {
MA=H*W;
rep(i, H+2) {
vector<int>P(W+2, H*W);
T.pb(P);
}
rep(i, H*W) {
T[R[i]+1][C[i]+1]=i;
gdzie[i]={R[i]+1, C[i]+1};
}
rep(i, N) tr[N+i]={N, 0};
rep(i, H*W) tr[N+i]={0, 1};
for(int i=N-1; i; --i) licz(i);
rep(i, H) rep(j, W) cnt(i+1, j+1, 1);
}
int swap_seats(int a, int b) {
rep(i, 5) {
int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
cnt(x, y, -1);
x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
cnt(x, y, -1);
}
swap(T[gdzie[a].st][gdzie[a].nd], T[gdzie[b].st][gdzie[b].nd]);
swap(gdzie[a], gdzie[b]);
rep(i, 5) {
int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
cnt(x, y, 1);
x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
cnt(x, y, 1);
}
return tr[1].nd;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
16884 KB |
Output is correct |
2 |
Correct |
50 ms |
16908 KB |
Output is correct |
3 |
Correct |
69 ms |
16876 KB |
Output is correct |
4 |
Correct |
40 ms |
16852 KB |
Output is correct |
5 |
Correct |
38 ms |
16904 KB |
Output is correct |
6 |
Correct |
58 ms |
16904 KB |
Output is correct |
7 |
Correct |
65 ms |
16884 KB |
Output is correct |
8 |
Correct |
57 ms |
16916 KB |
Output is correct |
9 |
Correct |
58 ms |
16972 KB |
Output is correct |
10 |
Correct |
65 ms |
16848 KB |
Output is correct |
11 |
Correct |
58 ms |
16892 KB |
Output is correct |
12 |
Correct |
36 ms |
16848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
16884 KB |
Output is correct |
2 |
Correct |
50 ms |
16908 KB |
Output is correct |
3 |
Correct |
69 ms |
16876 KB |
Output is correct |
4 |
Correct |
40 ms |
16852 KB |
Output is correct |
5 |
Correct |
38 ms |
16904 KB |
Output is correct |
6 |
Correct |
58 ms |
16904 KB |
Output is correct |
7 |
Correct |
65 ms |
16884 KB |
Output is correct |
8 |
Correct |
57 ms |
16916 KB |
Output is correct |
9 |
Correct |
58 ms |
16972 KB |
Output is correct |
10 |
Correct |
65 ms |
16848 KB |
Output is correct |
11 |
Correct |
58 ms |
16892 KB |
Output is correct |
12 |
Correct |
36 ms |
16848 KB |
Output is correct |
13 |
Correct |
103 ms |
17364 KB |
Output is correct |
14 |
Correct |
122 ms |
17388 KB |
Output is correct |
15 |
Correct |
65 ms |
17496 KB |
Output is correct |
16 |
Correct |
49 ms |
17912 KB |
Output is correct |
17 |
Correct |
82 ms |
17448 KB |
Output is correct |
18 |
Correct |
75 ms |
17364 KB |
Output is correct |
19 |
Correct |
72 ms |
17440 KB |
Output is correct |
20 |
Correct |
59 ms |
17696 KB |
Output is correct |
21 |
Correct |
47 ms |
17492 KB |
Output is correct |
22 |
Correct |
50 ms |
17892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2009 ms |
56360 KB |
Output is correct |
2 |
Correct |
898 ms |
72196 KB |
Output is correct |
3 |
Correct |
823 ms |
71912 KB |
Output is correct |
4 |
Correct |
698 ms |
71884 KB |
Output is correct |
5 |
Correct |
744 ms |
71968 KB |
Output is correct |
6 |
Correct |
673 ms |
71960 KB |
Output is correct |
7 |
Correct |
759 ms |
71944 KB |
Output is correct |
8 |
Correct |
771 ms |
72004 KB |
Output is correct |
9 |
Correct |
778 ms |
71884 KB |
Output is correct |
10 |
Correct |
773 ms |
71964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
17340 KB |
Output is correct |
2 |
Correct |
176 ms |
20852 KB |
Output is correct |
3 |
Correct |
702 ms |
56136 KB |
Output is correct |
4 |
Correct |
2001 ms |
72040 KB |
Output is correct |
5 |
Correct |
617 ms |
79796 KB |
Output is correct |
6 |
Correct |
1670 ms |
122808 KB |
Output is correct |
7 |
Correct |
721 ms |
75832 KB |
Output is correct |
8 |
Correct |
836 ms |
72032 KB |
Output is correct |
9 |
Correct |
770 ms |
72400 KB |
Output is correct |
10 |
Correct |
782 ms |
76708 KB |
Output is correct |
11 |
Correct |
721 ms |
94348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
157 ms |
18248 KB |
Output is correct |
2 |
Correct |
236 ms |
18468 KB |
Output is correct |
3 |
Correct |
275 ms |
18440 KB |
Output is correct |
4 |
Correct |
316 ms |
18528 KB |
Output is correct |
5 |
Correct |
463 ms |
18968 KB |
Output is correct |
6 |
Correct |
1078 ms |
66184 KB |
Output is correct |
7 |
Correct |
1236 ms |
68100 KB |
Output is correct |
8 |
Correct |
1031 ms |
64124 KB |
Output is correct |
9 |
Correct |
2100 ms |
67972 KB |
Output is correct |
10 |
Correct |
977 ms |
68092 KB |
Output is correct |
11 |
Correct |
1000 ms |
68104 KB |
Output is correct |
12 |
Correct |
1040 ms |
67996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
16884 KB |
Output is correct |
2 |
Correct |
50 ms |
16908 KB |
Output is correct |
3 |
Correct |
69 ms |
16876 KB |
Output is correct |
4 |
Correct |
40 ms |
16852 KB |
Output is correct |
5 |
Correct |
38 ms |
16904 KB |
Output is correct |
6 |
Correct |
58 ms |
16904 KB |
Output is correct |
7 |
Correct |
65 ms |
16884 KB |
Output is correct |
8 |
Correct |
57 ms |
16916 KB |
Output is correct |
9 |
Correct |
58 ms |
16972 KB |
Output is correct |
10 |
Correct |
65 ms |
16848 KB |
Output is correct |
11 |
Correct |
58 ms |
16892 KB |
Output is correct |
12 |
Correct |
36 ms |
16848 KB |
Output is correct |
13 |
Correct |
103 ms |
17364 KB |
Output is correct |
14 |
Correct |
122 ms |
17388 KB |
Output is correct |
15 |
Correct |
65 ms |
17496 KB |
Output is correct |
16 |
Correct |
49 ms |
17912 KB |
Output is correct |
17 |
Correct |
82 ms |
17448 KB |
Output is correct |
18 |
Correct |
75 ms |
17364 KB |
Output is correct |
19 |
Correct |
72 ms |
17440 KB |
Output is correct |
20 |
Correct |
59 ms |
17696 KB |
Output is correct |
21 |
Correct |
47 ms |
17492 KB |
Output is correct |
22 |
Correct |
50 ms |
17892 KB |
Output is correct |
23 |
Correct |
2009 ms |
56360 KB |
Output is correct |
24 |
Correct |
898 ms |
72196 KB |
Output is correct |
25 |
Correct |
823 ms |
71912 KB |
Output is correct |
26 |
Correct |
698 ms |
71884 KB |
Output is correct |
27 |
Correct |
744 ms |
71968 KB |
Output is correct |
28 |
Correct |
673 ms |
71960 KB |
Output is correct |
29 |
Correct |
759 ms |
71944 KB |
Output is correct |
30 |
Correct |
771 ms |
72004 KB |
Output is correct |
31 |
Correct |
778 ms |
71884 KB |
Output is correct |
32 |
Correct |
773 ms |
71964 KB |
Output is correct |
33 |
Correct |
96 ms |
17340 KB |
Output is correct |
34 |
Correct |
176 ms |
20852 KB |
Output is correct |
35 |
Correct |
702 ms |
56136 KB |
Output is correct |
36 |
Correct |
2001 ms |
72040 KB |
Output is correct |
37 |
Correct |
617 ms |
79796 KB |
Output is correct |
38 |
Correct |
1670 ms |
122808 KB |
Output is correct |
39 |
Correct |
721 ms |
75832 KB |
Output is correct |
40 |
Correct |
836 ms |
72032 KB |
Output is correct |
41 |
Correct |
770 ms |
72400 KB |
Output is correct |
42 |
Correct |
782 ms |
76708 KB |
Output is correct |
43 |
Correct |
721 ms |
94348 KB |
Output is correct |
44 |
Correct |
157 ms |
18248 KB |
Output is correct |
45 |
Correct |
236 ms |
18468 KB |
Output is correct |
46 |
Correct |
275 ms |
18440 KB |
Output is correct |
47 |
Correct |
316 ms |
18528 KB |
Output is correct |
48 |
Correct |
463 ms |
18968 KB |
Output is correct |
49 |
Correct |
1078 ms |
66184 KB |
Output is correct |
50 |
Correct |
1236 ms |
68100 KB |
Output is correct |
51 |
Correct |
1031 ms |
64124 KB |
Output is correct |
52 |
Correct |
2100 ms |
67972 KB |
Output is correct |
53 |
Correct |
977 ms |
68092 KB |
Output is correct |
54 |
Correct |
1000 ms |
68104 KB |
Output is correct |
55 |
Correct |
1040 ms |
67996 KB |
Output is correct |
56 |
Correct |
321 ms |
18472 KB |
Output is correct |
57 |
Correct |
605 ms |
18512 KB |
Output is correct |
58 |
Correct |
643 ms |
18956 KB |
Output is correct |
59 |
Correct |
1560 ms |
72908 KB |
Output is correct |
60 |
Correct |
3385 ms |
73008 KB |
Output is correct |
61 |
Correct |
1467 ms |
72992 KB |
Output is correct |
62 |
Correct |
1127 ms |
76728 KB |
Output is correct |
63 |
Correct |
3025 ms |
76792 KB |
Output is correct |
64 |
Correct |
1658 ms |
74076 KB |
Output is correct |
65 |
Correct |
1455 ms |
72992 KB |
Output is correct |
66 |
Correct |
1689 ms |
73200 KB |
Output is correct |
67 |
Correct |
1679 ms |
77580 KB |
Output is correct |
68 |
Correct |
1294 ms |
87216 KB |
Output is correct |
69 |
Correct |
2925 ms |
96360 KB |
Output is correct |