#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int n, m;
int tot;
int r[maxn];
struct node
{
int val, cnt, lz;
node(int a = 0, int b = 0) : val(a), cnt(b)
{
lz = 0;
}
};
node st[4*maxn];
node pull(node &x, node &y)
{
if(x.val< y.val) return x;
if(x.val> y.val) return y;
return node(x.val, x.cnt+y.cnt);
}
void pushdown(int p, int L, int R)
{
if(st[p].lz == 0) return;
st[p].val += st[p].lz;
if(L != R)
{
st[2*p].lz += st[p].lz;
st[2*p+1].lz += st[p].lz;
}
st[p].lz = 0;
}
void build(int p = 1, int L = 0, int R = tot-1)
{
if(L == R)
{
st[p] = node(0, 1);
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int dx, int p = 1, int L = 0, int R = tot-1)
{
pushdown(p, L, R);
if(i> j || i> R || j< L) return;
if(i<= L && R<= j)
{
st[p].lz += dx;
pushdown(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, 2*p, L, M);
update(i, j, dx, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = tot-1)
{
if(i> R || j< L) return node(1e9, 0);
pushdown(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
vector< vector<int> > bow;
int row[maxn];
int col[maxn];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void add(int x, int y, int a, int b)
{
// printf("add %d to [%d %d]\n", val, a, b);
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
// printf("%d ", pos);
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
// printf("\n");
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), 1);
update(max(a, t0), min(t1-1, b), -1);
update(max(a, t1), min(t2-1, b), 1);
update(max(a, t2), b, -1);
}
}
void rem(int x, int y, int a, int b)
{
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), -1);
update(max(a, t0), min(t1-1, b), 1);
update(max(a, t1), min(t2-1, b), -1);
update(max(a, t2), b, 1);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H; m = W;
tot = n*m;
bow.assign(n, vector<int>(m));
build();
int prv = 0;
for(int i = 0; i< tot; i++)
{
bow[R[i]][C[i]] = i;
row[i] = R[i];
col[i] = C[i];
}
for(int i = 0; i< tot; i++)
{
int cur = prv;
for(int base = 0; base< 8; base += 2)
{
int cnt = 0;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 0;
int x = row[i], y = col[i];
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]]< i;
}
cnt += loc;
}
if(cnt == 1 || cnt == 3) cur--;
else cur++;
}
update(i, i, cur);
// printf("f[%d] = %d\n", i, cur);
prv = cur;
}
// printf("(%d, %d)\n", kk.val, kk.cnt);
}
int swap_seats(int a, int b)
{
if(a> b) swap(a, b);
rem(row[a], col[a], a, b-1);
// printf("finished reming\n");
// printf("f' = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
swap(bow[row[a]][col[a]], bow[row[b]][col[b]]);
add(row[b], col[b], a, b-1);
swap(row[a], row[b]);
swap(col[a], col[b]);
node kk = ask(0, tot-1);
// printf("f = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
// printf("(%d, %d)\n", kk.val, kk.cnt);
if(kk.val == 4) return kk.cnt;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
47480 KB |
Output is correct |
2 |
Correct |
67 ms |
47536 KB |
Output is correct |
3 |
Correct |
72 ms |
47448 KB |
Output is correct |
4 |
Correct |
66 ms |
47480 KB |
Output is correct |
5 |
Correct |
66 ms |
47480 KB |
Output is correct |
6 |
Correct |
70 ms |
47500 KB |
Output is correct |
7 |
Correct |
71 ms |
47604 KB |
Output is correct |
8 |
Correct |
73 ms |
47480 KB |
Output is correct |
9 |
Correct |
77 ms |
47440 KB |
Output is correct |
10 |
Correct |
73 ms |
47536 KB |
Output is correct |
11 |
Correct |
72 ms |
47612 KB |
Output is correct |
12 |
Correct |
65 ms |
47480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
47480 KB |
Output is correct |
2 |
Correct |
67 ms |
47536 KB |
Output is correct |
3 |
Correct |
72 ms |
47448 KB |
Output is correct |
4 |
Correct |
66 ms |
47480 KB |
Output is correct |
5 |
Correct |
66 ms |
47480 KB |
Output is correct |
6 |
Correct |
70 ms |
47500 KB |
Output is correct |
7 |
Correct |
71 ms |
47604 KB |
Output is correct |
8 |
Correct |
73 ms |
47480 KB |
Output is correct |
9 |
Correct |
77 ms |
47440 KB |
Output is correct |
10 |
Correct |
73 ms |
47536 KB |
Output is correct |
11 |
Correct |
72 ms |
47612 KB |
Output is correct |
12 |
Correct |
65 ms |
47480 KB |
Output is correct |
13 |
Correct |
101 ms |
47840 KB |
Output is correct |
14 |
Correct |
103 ms |
47852 KB |
Output is correct |
15 |
Correct |
85 ms |
47876 KB |
Output is correct |
16 |
Correct |
83 ms |
48364 KB |
Output is correct |
17 |
Correct |
93 ms |
47864 KB |
Output is correct |
18 |
Correct |
96 ms |
47840 KB |
Output is correct |
19 |
Correct |
97 ms |
47864 KB |
Output is correct |
20 |
Correct |
91 ms |
48072 KB |
Output is correct |
21 |
Correct |
92 ms |
47880 KB |
Output is correct |
22 |
Correct |
97 ms |
48400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
984 ms |
90800 KB |
Output is correct |
2 |
Correct |
854 ms |
90776 KB |
Output is correct |
3 |
Correct |
856 ms |
90756 KB |
Output is correct |
4 |
Correct |
818 ms |
90776 KB |
Output is correct |
5 |
Correct |
831 ms |
90788 KB |
Output is correct |
6 |
Correct |
806 ms |
90776 KB |
Output is correct |
7 |
Correct |
830 ms |
90788 KB |
Output is correct |
8 |
Correct |
855 ms |
90896 KB |
Output is correct |
9 |
Correct |
838 ms |
90760 KB |
Output is correct |
10 |
Correct |
835 ms |
90776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
47856 KB |
Output is correct |
2 |
Correct |
168 ms |
51124 KB |
Output is correct |
3 |
Correct |
796 ms |
90776 KB |
Output is correct |
4 |
Correct |
982 ms |
90716 KB |
Output is correct |
5 |
Correct |
765 ms |
90804 KB |
Output is correct |
6 |
Correct |
1243 ms |
141616 KB |
Output is correct |
7 |
Correct |
810 ms |
90736 KB |
Output is correct |
8 |
Correct |
823 ms |
90780 KB |
Output is correct |
9 |
Correct |
844 ms |
91132 KB |
Output is correct |
10 |
Correct |
813 ms |
93828 KB |
Output is correct |
11 |
Correct |
851 ms |
113784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
49128 KB |
Output is correct |
2 |
Correct |
190 ms |
49040 KB |
Output is correct |
3 |
Correct |
262 ms |
49012 KB |
Output is correct |
4 |
Correct |
326 ms |
49088 KB |
Output is correct |
5 |
Correct |
413 ms |
49492 KB |
Output is correct |
6 |
Correct |
1320 ms |
91768 KB |
Output is correct |
7 |
Correct |
1357 ms |
91724 KB |
Output is correct |
8 |
Correct |
1291 ms |
91688 KB |
Output is correct |
9 |
Correct |
1505 ms |
91580 KB |
Output is correct |
10 |
Correct |
1231 ms |
91724 KB |
Output is correct |
11 |
Correct |
1227 ms |
91708 KB |
Output is correct |
12 |
Correct |
1225 ms |
91732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
47480 KB |
Output is correct |
2 |
Correct |
67 ms |
47536 KB |
Output is correct |
3 |
Correct |
72 ms |
47448 KB |
Output is correct |
4 |
Correct |
66 ms |
47480 KB |
Output is correct |
5 |
Correct |
66 ms |
47480 KB |
Output is correct |
6 |
Correct |
70 ms |
47500 KB |
Output is correct |
7 |
Correct |
71 ms |
47604 KB |
Output is correct |
8 |
Correct |
73 ms |
47480 KB |
Output is correct |
9 |
Correct |
77 ms |
47440 KB |
Output is correct |
10 |
Correct |
73 ms |
47536 KB |
Output is correct |
11 |
Correct |
72 ms |
47612 KB |
Output is correct |
12 |
Correct |
65 ms |
47480 KB |
Output is correct |
13 |
Correct |
101 ms |
47840 KB |
Output is correct |
14 |
Correct |
103 ms |
47852 KB |
Output is correct |
15 |
Correct |
85 ms |
47876 KB |
Output is correct |
16 |
Correct |
83 ms |
48364 KB |
Output is correct |
17 |
Correct |
93 ms |
47864 KB |
Output is correct |
18 |
Correct |
96 ms |
47840 KB |
Output is correct |
19 |
Correct |
97 ms |
47864 KB |
Output is correct |
20 |
Correct |
91 ms |
48072 KB |
Output is correct |
21 |
Correct |
92 ms |
47880 KB |
Output is correct |
22 |
Correct |
97 ms |
48400 KB |
Output is correct |
23 |
Correct |
984 ms |
90800 KB |
Output is correct |
24 |
Correct |
854 ms |
90776 KB |
Output is correct |
25 |
Correct |
856 ms |
90756 KB |
Output is correct |
26 |
Correct |
818 ms |
90776 KB |
Output is correct |
27 |
Correct |
831 ms |
90788 KB |
Output is correct |
28 |
Correct |
806 ms |
90776 KB |
Output is correct |
29 |
Correct |
830 ms |
90788 KB |
Output is correct |
30 |
Correct |
855 ms |
90896 KB |
Output is correct |
31 |
Correct |
838 ms |
90760 KB |
Output is correct |
32 |
Correct |
835 ms |
90776 KB |
Output is correct |
33 |
Correct |
106 ms |
47856 KB |
Output is correct |
34 |
Correct |
168 ms |
51124 KB |
Output is correct |
35 |
Correct |
796 ms |
90776 KB |
Output is correct |
36 |
Correct |
982 ms |
90716 KB |
Output is correct |
37 |
Correct |
765 ms |
90804 KB |
Output is correct |
38 |
Correct |
1243 ms |
141616 KB |
Output is correct |
39 |
Correct |
810 ms |
90736 KB |
Output is correct |
40 |
Correct |
823 ms |
90780 KB |
Output is correct |
41 |
Correct |
844 ms |
91132 KB |
Output is correct |
42 |
Correct |
813 ms |
93828 KB |
Output is correct |
43 |
Correct |
851 ms |
113784 KB |
Output is correct |
44 |
Correct |
156 ms |
49128 KB |
Output is correct |
45 |
Correct |
190 ms |
49040 KB |
Output is correct |
46 |
Correct |
262 ms |
49012 KB |
Output is correct |
47 |
Correct |
326 ms |
49088 KB |
Output is correct |
48 |
Correct |
413 ms |
49492 KB |
Output is correct |
49 |
Correct |
1320 ms |
91768 KB |
Output is correct |
50 |
Correct |
1357 ms |
91724 KB |
Output is correct |
51 |
Correct |
1291 ms |
91688 KB |
Output is correct |
52 |
Correct |
1505 ms |
91580 KB |
Output is correct |
53 |
Correct |
1231 ms |
91724 KB |
Output is correct |
54 |
Correct |
1227 ms |
91708 KB |
Output is correct |
55 |
Correct |
1225 ms |
91732 KB |
Output is correct |
56 |
Correct |
198 ms |
48996 KB |
Output is correct |
57 |
Correct |
321 ms |
49032 KB |
Output is correct |
58 |
Correct |
560 ms |
49388 KB |
Output is correct |
59 |
Correct |
1644 ms |
91644 KB |
Output is correct |
60 |
Correct |
1866 ms |
91740 KB |
Output is correct |
61 |
Correct |
1578 ms |
91644 KB |
Output is correct |
62 |
Correct |
1319 ms |
91696 KB |
Output is correct |
63 |
Correct |
1761 ms |
91692 KB |
Output is correct |
64 |
Correct |
1595 ms |
91640 KB |
Output is correct |
65 |
Correct |
1521 ms |
91732 KB |
Output is correct |
66 |
Correct |
1717 ms |
92080 KB |
Output is correct |
67 |
Correct |
1616 ms |
94828 KB |
Output is correct |
68 |
Correct |
1440 ms |
106068 KB |
Output is correct |
69 |
Correct |
1958 ms |
115148 KB |
Output is correct |