#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#define endl '\n'
#endif
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
ll pwr(ll a,ll b){
a %= mod;
int ans = 1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
const int N = 1e6 + 5;
pair<int,int> tr[2 * N][2];
int tot;
int d[2 * N];
pii pos[N];
int n, h;
void build1(){
n = tot + 1;
h = sizeof(int) * 8 - __builtin_clz(n);
fr(i, n, 2 * n - 1){
tr[i][0].fi = 0, tr[i][0].se = 1;
tr[i][1].fi = 1e9, tr[i][1].se = 0;
}
for(int i = n - 1; i > 0; i--){
tr[i][0].fi = 0, tr[i][0].se = tr[i << 1][0].se + tr[i << 1 | 1][0].se;
tr[i][1].fi = 1e9, tr[i][1].se = 0;
}
}
vector<vector<int>> m;
vector<vector<bool>> active;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {0, -1, 0, -1};
int pp[4] = {1, 2, 2, 1};
void apply(int p, int value){
tr[p][0].fi += value;
tr[p][1].fi += value;
if(p < n) d[p] += value;
}
void push(int p){
for(int s = h; s > 0; --s){
int i = p >> s;
if (d[i] != 0){
apply(i << 1, d[i]);
apply(i << 1 | 1, d[i]);
d[i] = 0;
}
}
}
void build(int nd) {
while(nd > 1){
nd >>= 1;
int pt1 = 0, pt2 = 0, pt = 0;
int nd1 = nd << 1, nd2 = nd1 | 1;
while(pt1 < 2 && pt2 < 2 && pt < 2){
if(tr[nd1][pt1].fi < tr[nd2][pt2].fi){
tr[nd][pt++] = tr[nd1][pt1++];
}
else if(tr[nd1][pt1].fi > tr[nd2][pt2].fi){
tr[nd][pt++] = tr[nd2][pt2++];
}
else{
tr[nd][pt++] = {tr[nd1][pt1].fi, tr[nd1][pt1].se + tr[nd2][pt2].se};
pt1++, pt2++;
}
}
tr[nd][0].fi += d[nd];
tr[nd][1].fi += d[nd];
}
}
void inc(int l, int r, int value){
r++;
l += n, r += n;
int l0 = l, r0 = r;
for(;l < r; l >>= 1, r >>= 1){
if(l & 1) apply(l++, value);
if(r & 1) apply(--r, value);
}
build(l0);
build(r0 - 1);
}
vector<pii> lol;
void add_box(int x,int y,int val){
if(!active[x][y] && val == -1) return;
if(active[x][y] && val == 1) return;
active[x][y] = !active[x][y];
x++, y++;
fr(i, 0, 3)
lol.pb({m[x + dx[i]][y + dy[i]], pp[i]});
sort(all(lol));
if(lol[0].fi <= tot && lol[0].fi == m[x][y])
inc(lol[0].fi, min(lol[1].fi - 1, tot), val);
if(lol[0].se == lol[1].se && lol[1].fi <= tot)
inc(lol[1].fi, min(lol[3].fi - 1, tot), 2 * val);
else if(lol[2].fi <= tot)
inc(lol[2].fi, min(lol[3].fi - 1, tot), 2 * val);
lol.clear();
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
tot = h * w - 1;
build1();
m.resize(h + 2);
active.resize(h + 2);
fr(i, 0, h + 1){
m[i].resize(w + 2, 1e9);
active[i].resize(w + 2, 0);
}
fr(i, 0, tot){
pos[i] = {r[i] + 1, c[i] + 1};
m[r[i] + 1][c[i] + 1] = i;
}
for(int i = 0; i <= h; i++){
for(int j = 0; j <= w; j++){
add_box(i, j, 1);
}
}
}
int swap_seats(int a,int b){
fr(i, 0, 3){
add_box(pos[a].fi + dx[i], pos[a].se + dy[i], -1);
add_box(pos[b].fi + dx[i], pos[b].se + dy[i], -1);
}
swap(pos[a], pos[b]);
m[pos[a].fi][pos[a].se] = a;
m[pos[b].fi][pos[b].se] = b;
fr(i, 0, 3){
add_box(pos[a].fi + dx[i], pos[a].se + dy[i], 1);
add_box(pos[b].fi + dx[i], pos[b].se + dy[i], 1);
}
int ans = 0;
fr(i, 0, 1){
if(tr[1][i].fi == 1){
ans = tr[1][i].se;
break;
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
512 KB |
Output is correct |
2 |
Correct |
18 ms |
512 KB |
Output is correct |
3 |
Correct |
22 ms |
504 KB |
Output is correct |
4 |
Correct |
12 ms |
512 KB |
Output is correct |
5 |
Correct |
9 ms |
512 KB |
Output is correct |
6 |
Correct |
18 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
21 ms |
512 KB |
Output is correct |
9 |
Correct |
21 ms |
504 KB |
Output is correct |
10 |
Correct |
21 ms |
512 KB |
Output is correct |
11 |
Correct |
21 ms |
512 KB |
Output is correct |
12 |
Correct |
11 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
512 KB |
Output is correct |
2 |
Correct |
18 ms |
512 KB |
Output is correct |
3 |
Correct |
22 ms |
504 KB |
Output is correct |
4 |
Correct |
12 ms |
512 KB |
Output is correct |
5 |
Correct |
9 ms |
512 KB |
Output is correct |
6 |
Correct |
18 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
21 ms |
512 KB |
Output is correct |
9 |
Correct |
21 ms |
504 KB |
Output is correct |
10 |
Correct |
21 ms |
512 KB |
Output is correct |
11 |
Correct |
21 ms |
512 KB |
Output is correct |
12 |
Correct |
11 ms |
512 KB |
Output is correct |
13 |
Correct |
43 ms |
1024 KB |
Output is correct |
14 |
Correct |
52 ms |
1024 KB |
Output is correct |
15 |
Correct |
23 ms |
1152 KB |
Output is correct |
16 |
Correct |
19 ms |
2304 KB |
Output is correct |
17 |
Correct |
35 ms |
1144 KB |
Output is correct |
18 |
Correct |
45 ms |
1088 KB |
Output is correct |
19 |
Correct |
37 ms |
1152 KB |
Output is correct |
20 |
Correct |
39 ms |
1656 KB |
Output is correct |
21 |
Correct |
30 ms |
1144 KB |
Output is correct |
22 |
Correct |
25 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1628 ms |
63352 KB |
Output is correct |
2 |
Correct |
945 ms |
63356 KB |
Output is correct |
3 |
Correct |
972 ms |
63352 KB |
Output is correct |
4 |
Correct |
688 ms |
59920 KB |
Output is correct |
5 |
Correct |
675 ms |
63456 KB |
Output is correct |
6 |
Correct |
1059 ms |
63352 KB |
Output is correct |
7 |
Correct |
923 ms |
63224 KB |
Output is correct |
8 |
Correct |
749 ms |
60408 KB |
Output is correct |
9 |
Correct |
982 ms |
59512 KB |
Output is correct |
10 |
Correct |
968 ms |
61432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
1024 KB |
Output is correct |
2 |
Correct |
132 ms |
6008 KB |
Output is correct |
3 |
Correct |
762 ms |
63324 KB |
Output is correct |
4 |
Correct |
1573 ms |
63328 KB |
Output is correct |
5 |
Correct |
767 ms |
67448 KB |
Output is correct |
6 |
Correct |
1556 ms |
184568 KB |
Output is correct |
7 |
Correct |
667 ms |
63964 KB |
Output is correct |
8 |
Correct |
1218 ms |
63224 KB |
Output is correct |
9 |
Correct |
803 ms |
60792 KB |
Output is correct |
10 |
Correct |
921 ms |
74872 KB |
Output is correct |
11 |
Correct |
934 ms |
118892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
1524 KB |
Output is correct |
2 |
Correct |
89 ms |
1400 KB |
Output is correct |
3 |
Correct |
85 ms |
1444 KB |
Output is correct |
4 |
Correct |
105 ms |
1476 KB |
Output is correct |
5 |
Correct |
177 ms |
2044 KB |
Output is correct |
6 |
Correct |
910 ms |
69724 KB |
Output is correct |
7 |
Correct |
1039 ms |
71672 KB |
Output is correct |
8 |
Correct |
1191 ms |
67704 KB |
Output is correct |
9 |
Correct |
1556 ms |
71800 KB |
Output is correct |
10 |
Correct |
827 ms |
67804 KB |
Output is correct |
11 |
Correct |
965 ms |
67832 KB |
Output is correct |
12 |
Correct |
579 ms |
67832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
512 KB |
Output is correct |
2 |
Correct |
18 ms |
512 KB |
Output is correct |
3 |
Correct |
22 ms |
504 KB |
Output is correct |
4 |
Correct |
12 ms |
512 KB |
Output is correct |
5 |
Correct |
9 ms |
512 KB |
Output is correct |
6 |
Correct |
18 ms |
504 KB |
Output is correct |
7 |
Correct |
20 ms |
504 KB |
Output is correct |
8 |
Correct |
21 ms |
512 KB |
Output is correct |
9 |
Correct |
21 ms |
504 KB |
Output is correct |
10 |
Correct |
21 ms |
512 KB |
Output is correct |
11 |
Correct |
21 ms |
512 KB |
Output is correct |
12 |
Correct |
11 ms |
512 KB |
Output is correct |
13 |
Correct |
43 ms |
1024 KB |
Output is correct |
14 |
Correct |
52 ms |
1024 KB |
Output is correct |
15 |
Correct |
23 ms |
1152 KB |
Output is correct |
16 |
Correct |
19 ms |
2304 KB |
Output is correct |
17 |
Correct |
35 ms |
1144 KB |
Output is correct |
18 |
Correct |
45 ms |
1088 KB |
Output is correct |
19 |
Correct |
37 ms |
1152 KB |
Output is correct |
20 |
Correct |
39 ms |
1656 KB |
Output is correct |
21 |
Correct |
30 ms |
1144 KB |
Output is correct |
22 |
Correct |
25 ms |
2296 KB |
Output is correct |
23 |
Correct |
1628 ms |
63352 KB |
Output is correct |
24 |
Correct |
945 ms |
63356 KB |
Output is correct |
25 |
Correct |
972 ms |
63352 KB |
Output is correct |
26 |
Correct |
688 ms |
59920 KB |
Output is correct |
27 |
Correct |
675 ms |
63456 KB |
Output is correct |
28 |
Correct |
1059 ms |
63352 KB |
Output is correct |
29 |
Correct |
923 ms |
63224 KB |
Output is correct |
30 |
Correct |
749 ms |
60408 KB |
Output is correct |
31 |
Correct |
982 ms |
59512 KB |
Output is correct |
32 |
Correct |
968 ms |
61432 KB |
Output is correct |
33 |
Correct |
83 ms |
1024 KB |
Output is correct |
34 |
Correct |
132 ms |
6008 KB |
Output is correct |
35 |
Correct |
762 ms |
63324 KB |
Output is correct |
36 |
Correct |
1573 ms |
63328 KB |
Output is correct |
37 |
Correct |
767 ms |
67448 KB |
Output is correct |
38 |
Correct |
1556 ms |
184568 KB |
Output is correct |
39 |
Correct |
667 ms |
63964 KB |
Output is correct |
40 |
Correct |
1218 ms |
63224 KB |
Output is correct |
41 |
Correct |
803 ms |
60792 KB |
Output is correct |
42 |
Correct |
921 ms |
74872 KB |
Output is correct |
43 |
Correct |
934 ms |
118892 KB |
Output is correct |
44 |
Correct |
73 ms |
1524 KB |
Output is correct |
45 |
Correct |
89 ms |
1400 KB |
Output is correct |
46 |
Correct |
85 ms |
1444 KB |
Output is correct |
47 |
Correct |
105 ms |
1476 KB |
Output is correct |
48 |
Correct |
177 ms |
2044 KB |
Output is correct |
49 |
Correct |
910 ms |
69724 KB |
Output is correct |
50 |
Correct |
1039 ms |
71672 KB |
Output is correct |
51 |
Correct |
1191 ms |
67704 KB |
Output is correct |
52 |
Correct |
1556 ms |
71800 KB |
Output is correct |
53 |
Correct |
827 ms |
67804 KB |
Output is correct |
54 |
Correct |
965 ms |
67832 KB |
Output is correct |
55 |
Correct |
579 ms |
67832 KB |
Output is correct |
56 |
Correct |
107 ms |
2036 KB |
Output is correct |
57 |
Correct |
215 ms |
2248 KB |
Output is correct |
58 |
Correct |
347 ms |
2920 KB |
Output is correct |
59 |
Correct |
1648 ms |
70564 KB |
Output is correct |
60 |
Correct |
2645 ms |
70944 KB |
Output is correct |
61 |
Correct |
1381 ms |
70136 KB |
Output is correct |
62 |
Correct |
1168 ms |
73544 KB |
Output is correct |
63 |
Correct |
2377 ms |
76124 KB |
Output is correct |
64 |
Correct |
1610 ms |
74172 KB |
Output is correct |
65 |
Correct |
1332 ms |
69752 KB |
Output is correct |
66 |
Correct |
1692 ms |
71696 KB |
Output is correct |
67 |
Correct |
1572 ms |
84992 KB |
Output is correct |
68 |
Correct |
1193 ms |
109276 KB |
Output is correct |
69 |
Correct |
2285 ms |
131908 KB |
Output is correct |