#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf = 1e9;
const int sz = 1<<20;
struct node {
int mn=inf, cnt=0;
node(int a, int b) {mn=a,cnt=b;}
node() {}
};
node t[2*sz];
int lazy[4*sz];
void merge(int v) {
if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
else t[v]=t[2*v+2];
}
void build(int v, int l, int r) {
if (r-l==1) return;
int m=(l+r)>>1;
build(2*v+1,l,m);
build(2*v+2,m,r);
merge(v);
}
void init(int n, int m) {
forn(i,n*m) t[sz-1+i]={0,1};
build(0,0,sz);
}
void push(int v) {
t[v].mn+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[2*v+2]+=lazy[v];
lazy[v]=0;
}
void add(int v, int l, int r, int lx, int rx, int x) {
if (lazy[v]) push(v);
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
lazy[v]+=x;
push(v);
return;
}
int m=(l+r)>>1;
if (m>lx) add(2*v+1,l,m,lx,rx,x);
else if (lazy[2*v+1]) push(2*v+1);
if (m<rx) add(2*v+2,m,r,lx,rx,x);
else if (lazy[2*v+2]) push(2*v+2);
merge(v);
}
void add(int l, int r, int x) {
if (l>=r) return;
add(0,0,sz,l,r,x);
}
int R[sz], C[sz];
int swapped=0;
int n,m;
vector<vector<int>> a;
void check(int i, int j, int x) {
vector<int> v = {a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]};
sort(all(v));
add(v[0],v[1],x);
add(v[2],v[3],x);
}
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n=_n, m=_m;
if (n==1 && m==1) return;
forn(i,n*m) R[i]=_r[i]+1, C[i]=_c[i]+1;
if (m==1) {
swap(n,m);
forn(i,n*m) swap(R[i],C[i]);
swapped=1;
}
init(n,m);
a.assign(n+2,vector<int>(m+2,n*m));
forn(i,n*m) a[R[i]][C[i]]=i;
for (int i=0; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
check(i,j,1);
}
}
}
int swap_seats(int x, int y) {
if (n==1 && m==1) return 1;
int p=R[x], q=C[x], u=R[y], v=C[y];
vector<int> z;
check(p,q,-1);
check(p-1,q-1,-1);
check(p-1,q,-1);
check(p,q-1,-1);
p=u, q=v;
check(p,q,-1);
check(p-1,q-1,-1);
check(p-1,q,-1);
check(p,q-1,-1);
swap(R[x],R[y]);
swap(C[x],C[y]);
a[R[x]][C[x]]=x;
a[R[y]][C[y]]=y;
p=R[x], q=C[x], u=R[y], v=C[y];
check(p,q,1);
check(p-1,q-1,1);
check(p-1,q,1);
check(p,q-1,1);
p=u, q=v;
check(p,q,1);
check(p-1,q-1,1);
check(p-1,q,1);
check(p,q-1,1);
return t[0].cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
16852 KB |
Output is correct |
2 |
Correct |
45 ms |
16880 KB |
Output is correct |
3 |
Correct |
58 ms |
16864 KB |
Output is correct |
4 |
Correct |
34 ms |
16900 KB |
Output is correct |
5 |
Correct |
39 ms |
16892 KB |
Output is correct |
6 |
Correct |
43 ms |
16860 KB |
Output is correct |
7 |
Correct |
45 ms |
16852 KB |
Output is correct |
8 |
Correct |
52 ms |
16856 KB |
Output is correct |
9 |
Correct |
43 ms |
16828 KB |
Output is correct |
10 |
Correct |
46 ms |
16876 KB |
Output is correct |
11 |
Correct |
42 ms |
16892 KB |
Output is correct |
12 |
Correct |
33 ms |
16856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
16852 KB |
Output is correct |
2 |
Correct |
45 ms |
16880 KB |
Output is correct |
3 |
Correct |
58 ms |
16864 KB |
Output is correct |
4 |
Correct |
34 ms |
16900 KB |
Output is correct |
5 |
Correct |
39 ms |
16892 KB |
Output is correct |
6 |
Correct |
43 ms |
16860 KB |
Output is correct |
7 |
Correct |
45 ms |
16852 KB |
Output is correct |
8 |
Correct |
52 ms |
16856 KB |
Output is correct |
9 |
Correct |
43 ms |
16828 KB |
Output is correct |
10 |
Correct |
46 ms |
16876 KB |
Output is correct |
11 |
Correct |
42 ms |
16892 KB |
Output is correct |
12 |
Correct |
33 ms |
16856 KB |
Output is correct |
13 |
Correct |
97 ms |
17440 KB |
Output is correct |
14 |
Correct |
89 ms |
17432 KB |
Output is correct |
15 |
Correct |
56 ms |
17532 KB |
Output is correct |
16 |
Correct |
47 ms |
17536 KB |
Output is correct |
17 |
Correct |
71 ms |
17476 KB |
Output is correct |
18 |
Correct |
68 ms |
17444 KB |
Output is correct |
19 |
Correct |
69 ms |
17464 KB |
Output is correct |
20 |
Correct |
48 ms |
17660 KB |
Output is correct |
21 |
Correct |
38 ms |
17520 KB |
Output is correct |
22 |
Correct |
52 ms |
17484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2032 ms |
60656 KB |
Output is correct |
2 |
Correct |
858 ms |
60480 KB |
Output is correct |
3 |
Correct |
723 ms |
60536 KB |
Output is correct |
4 |
Correct |
637 ms |
60488 KB |
Output is correct |
5 |
Correct |
638 ms |
60476 KB |
Output is correct |
6 |
Correct |
592 ms |
60772 KB |
Output is correct |
7 |
Correct |
725 ms |
60832 KB |
Output is correct |
8 |
Correct |
800 ms |
61068 KB |
Output is correct |
9 |
Correct |
725 ms |
61188 KB |
Output is correct |
10 |
Correct |
652 ms |
61092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
17524 KB |
Output is correct |
2 |
Correct |
135 ms |
21268 KB |
Output is correct |
3 |
Correct |
684 ms |
61296 KB |
Output is correct |
4 |
Correct |
1802 ms |
61380 KB |
Output is correct |
5 |
Correct |
540 ms |
69048 KB |
Output is correct |
6 |
Correct |
1822 ms |
69096 KB |
Output is correct |
7 |
Correct |
594 ms |
63904 KB |
Output is correct |
8 |
Correct |
774 ms |
61316 KB |
Output is correct |
9 |
Correct |
652 ms |
61764 KB |
Output is correct |
10 |
Correct |
708 ms |
65796 KB |
Output is correct |
11 |
Correct |
579 ms |
83868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
18376 KB |
Output is correct |
2 |
Correct |
178 ms |
18468 KB |
Output is correct |
3 |
Correct |
189 ms |
18520 KB |
Output is correct |
4 |
Correct |
224 ms |
18420 KB |
Output is correct |
5 |
Correct |
349 ms |
18932 KB |
Output is correct |
6 |
Correct |
904 ms |
68900 KB |
Output is correct |
7 |
Correct |
1140 ms |
69040 KB |
Output is correct |
8 |
Correct |
869 ms |
68952 KB |
Output is correct |
9 |
Correct |
2228 ms |
69064 KB |
Output is correct |
10 |
Correct |
833 ms |
69020 KB |
Output is correct |
11 |
Correct |
860 ms |
69036 KB |
Output is correct |
12 |
Correct |
787 ms |
68984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
16852 KB |
Output is correct |
2 |
Correct |
45 ms |
16880 KB |
Output is correct |
3 |
Correct |
58 ms |
16864 KB |
Output is correct |
4 |
Correct |
34 ms |
16900 KB |
Output is correct |
5 |
Correct |
39 ms |
16892 KB |
Output is correct |
6 |
Correct |
43 ms |
16860 KB |
Output is correct |
7 |
Correct |
45 ms |
16852 KB |
Output is correct |
8 |
Correct |
52 ms |
16856 KB |
Output is correct |
9 |
Correct |
43 ms |
16828 KB |
Output is correct |
10 |
Correct |
46 ms |
16876 KB |
Output is correct |
11 |
Correct |
42 ms |
16892 KB |
Output is correct |
12 |
Correct |
33 ms |
16856 KB |
Output is correct |
13 |
Correct |
97 ms |
17440 KB |
Output is correct |
14 |
Correct |
89 ms |
17432 KB |
Output is correct |
15 |
Correct |
56 ms |
17532 KB |
Output is correct |
16 |
Correct |
47 ms |
17536 KB |
Output is correct |
17 |
Correct |
71 ms |
17476 KB |
Output is correct |
18 |
Correct |
68 ms |
17444 KB |
Output is correct |
19 |
Correct |
69 ms |
17464 KB |
Output is correct |
20 |
Correct |
48 ms |
17660 KB |
Output is correct |
21 |
Correct |
38 ms |
17520 KB |
Output is correct |
22 |
Correct |
52 ms |
17484 KB |
Output is correct |
23 |
Correct |
2032 ms |
60656 KB |
Output is correct |
24 |
Correct |
858 ms |
60480 KB |
Output is correct |
25 |
Correct |
723 ms |
60536 KB |
Output is correct |
26 |
Correct |
637 ms |
60488 KB |
Output is correct |
27 |
Correct |
638 ms |
60476 KB |
Output is correct |
28 |
Correct |
592 ms |
60772 KB |
Output is correct |
29 |
Correct |
725 ms |
60832 KB |
Output is correct |
30 |
Correct |
800 ms |
61068 KB |
Output is correct |
31 |
Correct |
725 ms |
61188 KB |
Output is correct |
32 |
Correct |
652 ms |
61092 KB |
Output is correct |
33 |
Correct |
85 ms |
17524 KB |
Output is correct |
34 |
Correct |
135 ms |
21268 KB |
Output is correct |
35 |
Correct |
684 ms |
61296 KB |
Output is correct |
36 |
Correct |
1802 ms |
61380 KB |
Output is correct |
37 |
Correct |
540 ms |
69048 KB |
Output is correct |
38 |
Correct |
1822 ms |
69096 KB |
Output is correct |
39 |
Correct |
594 ms |
63904 KB |
Output is correct |
40 |
Correct |
774 ms |
61316 KB |
Output is correct |
41 |
Correct |
652 ms |
61764 KB |
Output is correct |
42 |
Correct |
708 ms |
65796 KB |
Output is correct |
43 |
Correct |
579 ms |
83868 KB |
Output is correct |
44 |
Correct |
196 ms |
18376 KB |
Output is correct |
45 |
Correct |
178 ms |
18468 KB |
Output is correct |
46 |
Correct |
189 ms |
18520 KB |
Output is correct |
47 |
Correct |
224 ms |
18420 KB |
Output is correct |
48 |
Correct |
349 ms |
18932 KB |
Output is correct |
49 |
Correct |
904 ms |
68900 KB |
Output is correct |
50 |
Correct |
1140 ms |
69040 KB |
Output is correct |
51 |
Correct |
869 ms |
68952 KB |
Output is correct |
52 |
Correct |
2228 ms |
69064 KB |
Output is correct |
53 |
Correct |
833 ms |
69020 KB |
Output is correct |
54 |
Correct |
860 ms |
69036 KB |
Output is correct |
55 |
Correct |
787 ms |
68984 KB |
Output is correct |
56 |
Correct |
244 ms |
18368 KB |
Output is correct |
57 |
Correct |
368 ms |
18432 KB |
Output is correct |
58 |
Correct |
433 ms |
18916 KB |
Output is correct |
59 |
Correct |
1332 ms |
61216 KB |
Output is correct |
60 |
Correct |
2755 ms |
61204 KB |
Output is correct |
61 |
Correct |
1137 ms |
61104 KB |
Output is correct |
62 |
Correct |
919 ms |
65032 KB |
Output is correct |
63 |
Correct |
2558 ms |
63748 KB |
Output is correct |
64 |
Correct |
1398 ms |
62044 KB |
Output is correct |
65 |
Correct |
1136 ms |
61260 KB |
Output is correct |
66 |
Correct |
1343 ms |
61400 KB |
Output is correct |
67 |
Correct |
1378 ms |
66020 KB |
Output is correct |
68 |
Correct |
1012 ms |
75488 KB |
Output is correct |
69 |
Correct |
2257 ms |
84596 KB |
Output is correct |