#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long
#define pll pair <ll,ll>
#define all(v) v.begin(),v.end()
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 1e6 + 10;
int n,m,k;
pii c[N];
int cnt[N * 4];
pii t[N * 4],t1[N * 4];
void merge(int v) {
t[v] = min(t[v + v],t[v + v + 1]);
cnt[v] = 0;
if(t[v + v] == t[v])cnt[v] += cnt[v + v];
if(t[v + v + 1] == t[v])cnt[v] += cnt[v + v + 1];
}
void push(int v) {
if(t1[v].f) {
t[v + v].f += t1[v].f;
t[v + v + 1].f += t1[v].f;
t1[v + v].f += t1[v].f;
t1[v + v + 1].f += t1[v].f;
t1[v].f = 0;
}
if(t1[v].s) {
t[v + v].s += t1[v].s;
t[v + v + 1].s += t1[v].s;
t1[v + v].s += t1[v].s;
t1[v + v + 1].s += t1[v].s;
t1[v].s = 0;
}
}
void upd(int v,int tl,int tr,int l,int r,int x,bool typ) {
if(tl > r || tr < l)return;
if(tl >= l && tr <= r) {
if(!typ) {
t[v].f += x;
t1[v].f += x;
}else {
t[v].s += x;
t1[v].s += x;
}
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(v + v,tl,tm,l,r,x,typ);
upd(v + v + 1,tm + 1,tr,l,r,x,typ);
merge(v);
}
void out(int v,int tl,int tr) {
cout << tl << " " << tr << " with " << t[v].f << " " << t[v].s << " and " << cnt[v] << endl;
if(tl == tr)return;
push(v);
int tm = (tl + tr) / 2;
out(v + v,tl,tm);
out(v + v + 1,tm + 1,tr);
}
vector <vector <int> > num,was1;
int tim;
int dob[N],dob1[N],L,R;
void change(int x,int y,int delt,int typ = -1) {
if(was1[x][y] == tim)return;
was1[x][y] = tim;
int mn = k + 10,mn1 = k + 10,mx = -1,mx1 = -1;
for(int i = x;i <= x + 1;i++) {
for(int j = y;j <= y + 1;j++) {
if(i <= 0 || i > n || j <= 0 || j > m) {
mx1 = mx;
mx = k + 1;
if(k + 1 < mn) {
mn1 = mn;
mn = k + 1;
}else {
mn1 = min(mn1,k + 1);
}
continue;
}
if(num[i][j] < mn) {
mn1 = mn;
mn = num[i][j];
}else {
mn1 = min(mn1,num[i][j]);
}
if(num[i][j] > mx) {
mx1 = mx;
mx = num[i][j];
}else {
mx1 = max(mx1,num[i][j]);
}
}
}
if(typ == 1) {
dob[mn] += delt;
dob[mn1] -= delt;
dob1[mx1] += delt;
dob1[mx] -= delt;
return;
}
if(mn1 - 1 >= L && mn <= R)upd(1,0,k,max(mn,L),min(mn1 - 1,R),delt,1);
if(mx - 1 >= L && mx1 <= R)upd(1,0,k,max(mx1,L),min(mx - 1,R),delt,0);
}
void add(int x,int typ = -1) {
for(int i = -1;i <= 0;i++) {
for(int j = -1;j <= 0;j++) {
change(c[x].f + i,c[x].s + j,1,typ);
}
}
}
void del(int x) {
for(int i = -1;i <= 0;i++) {
for(int j = -1;j <= 0;j++) {
change(c[x].f + i,c[x].s + j,-1,-1);
}
}
}
pii d[N];
void build(int v,int tl,int tr) {
if(tl == tr) {
t[v] = d[tl];
cnt[v] = 1;
return;
}
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
merge(v);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
vector <int> empt;
empt.assign(m + 1,0);
num.assign(n + 1,empt);
was1 = num;
k = n * m - 1;
for(int i = 0;i <= k;i++) {
c[i] = mp(R[i] + 1,C[i] + 1);
num[c[i].f][c[i].s] = i;
}
// cout << "well" << endl;
++tim;
for(int i = 0;i <= k;i++) {
// cout << i << endl;
add(i,1);
}
int tek = 0,tek1 = 0;
for(int i = 0;i <= k;i++) {
tek += dob[i];
tek1 += dob1[i];
d[i] = mp(tek1,tek);
}
build(1,0,k);
// out(1,0,k);
}
int swap_seats(int a, int b) {
if(a > b)swap(a,b);
L = a;
R = b;
++tim;
del(a);
del(b);
swap(c[a],c[b]);
num[c[a].f][c[a].s] = a;
num[c[b].f][c[b].s] = b;
++tim;
add(a);
add(b);
// out(1,0,k);
return cnt[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
17 ms |
468 KB |
Output is correct |
3 |
Correct |
24 ms |
532 KB |
Output is correct |
4 |
Correct |
17 ms |
496 KB |
Output is correct |
5 |
Correct |
14 ms |
520 KB |
Output is correct |
6 |
Correct |
23 ms |
596 KB |
Output is correct |
7 |
Correct |
22 ms |
488 KB |
Output is correct |
8 |
Correct |
27 ms |
480 KB |
Output is correct |
9 |
Correct |
24 ms |
488 KB |
Output is correct |
10 |
Correct |
24 ms |
596 KB |
Output is correct |
11 |
Correct |
22 ms |
480 KB |
Output is correct |
12 |
Correct |
17 ms |
480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
17 ms |
468 KB |
Output is correct |
3 |
Correct |
24 ms |
532 KB |
Output is correct |
4 |
Correct |
17 ms |
496 KB |
Output is correct |
5 |
Correct |
14 ms |
520 KB |
Output is correct |
6 |
Correct |
23 ms |
596 KB |
Output is correct |
7 |
Correct |
22 ms |
488 KB |
Output is correct |
8 |
Correct |
27 ms |
480 KB |
Output is correct |
9 |
Correct |
24 ms |
488 KB |
Output is correct |
10 |
Correct |
24 ms |
596 KB |
Output is correct |
11 |
Correct |
22 ms |
480 KB |
Output is correct |
12 |
Correct |
17 ms |
480 KB |
Output is correct |
13 |
Correct |
51 ms |
1660 KB |
Output is correct |
14 |
Correct |
48 ms |
1608 KB |
Output is correct |
15 |
Correct |
33 ms |
1868 KB |
Output is correct |
16 |
Correct |
31 ms |
2668 KB |
Output is correct |
17 |
Correct |
42 ms |
1724 KB |
Output is correct |
18 |
Correct |
54 ms |
1668 KB |
Output is correct |
19 |
Correct |
42 ms |
1768 KB |
Output is correct |
20 |
Correct |
38 ms |
2132 KB |
Output is correct |
21 |
Correct |
30 ms |
1748 KB |
Output is correct |
22 |
Correct |
31 ms |
2668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
542 ms |
96680 KB |
Output is correct |
2 |
Correct |
371 ms |
96740 KB |
Output is correct |
3 |
Correct |
393 ms |
96524 KB |
Output is correct |
4 |
Correct |
395 ms |
96620 KB |
Output is correct |
5 |
Correct |
385 ms |
96624 KB |
Output is correct |
6 |
Correct |
381 ms |
96556 KB |
Output is correct |
7 |
Correct |
382 ms |
96688 KB |
Output is correct |
8 |
Correct |
394 ms |
96676 KB |
Output is correct |
9 |
Correct |
391 ms |
96272 KB |
Output is correct |
10 |
Correct |
382 ms |
96424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
1620 KB |
Output is correct |
2 |
Correct |
91 ms |
10416 KB |
Output is correct |
3 |
Correct |
357 ms |
96172 KB |
Output is correct |
4 |
Correct |
461 ms |
96444 KB |
Output is correct |
5 |
Correct |
359 ms |
99636 KB |
Output is correct |
6 |
Correct |
959 ms |
194124 KB |
Output is correct |
7 |
Correct |
374 ms |
99108 KB |
Output is correct |
8 |
Correct |
382 ms |
96620 KB |
Output is correct |
9 |
Correct |
392 ms |
97204 KB |
Output is correct |
10 |
Correct |
400 ms |
105528 KB |
Output is correct |
11 |
Correct |
413 ms |
142648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
1968 KB |
Output is correct |
2 |
Correct |
94 ms |
2036 KB |
Output is correct |
3 |
Correct |
149 ms |
1992 KB |
Output is correct |
4 |
Correct |
211 ms |
2092 KB |
Output is correct |
5 |
Correct |
281 ms |
3308 KB |
Output is correct |
6 |
Correct |
819 ms |
102184 KB |
Output is correct |
7 |
Correct |
853 ms |
102128 KB |
Output is correct |
8 |
Correct |
809 ms |
102392 KB |
Output is correct |
9 |
Correct |
1054 ms |
102456 KB |
Output is correct |
10 |
Correct |
762 ms |
102320 KB |
Output is correct |
11 |
Correct |
733 ms |
102240 KB |
Output is correct |
12 |
Correct |
762 ms |
102192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
468 KB |
Output is correct |
2 |
Correct |
17 ms |
468 KB |
Output is correct |
3 |
Correct |
24 ms |
532 KB |
Output is correct |
4 |
Correct |
17 ms |
496 KB |
Output is correct |
5 |
Correct |
14 ms |
520 KB |
Output is correct |
6 |
Correct |
23 ms |
596 KB |
Output is correct |
7 |
Correct |
22 ms |
488 KB |
Output is correct |
8 |
Correct |
27 ms |
480 KB |
Output is correct |
9 |
Correct |
24 ms |
488 KB |
Output is correct |
10 |
Correct |
24 ms |
596 KB |
Output is correct |
11 |
Correct |
22 ms |
480 KB |
Output is correct |
12 |
Correct |
17 ms |
480 KB |
Output is correct |
13 |
Correct |
51 ms |
1660 KB |
Output is correct |
14 |
Correct |
48 ms |
1608 KB |
Output is correct |
15 |
Correct |
33 ms |
1868 KB |
Output is correct |
16 |
Correct |
31 ms |
2668 KB |
Output is correct |
17 |
Correct |
42 ms |
1724 KB |
Output is correct |
18 |
Correct |
54 ms |
1668 KB |
Output is correct |
19 |
Correct |
42 ms |
1768 KB |
Output is correct |
20 |
Correct |
38 ms |
2132 KB |
Output is correct |
21 |
Correct |
30 ms |
1748 KB |
Output is correct |
22 |
Correct |
31 ms |
2668 KB |
Output is correct |
23 |
Correct |
542 ms |
96680 KB |
Output is correct |
24 |
Correct |
371 ms |
96740 KB |
Output is correct |
25 |
Correct |
393 ms |
96524 KB |
Output is correct |
26 |
Correct |
395 ms |
96620 KB |
Output is correct |
27 |
Correct |
385 ms |
96624 KB |
Output is correct |
28 |
Correct |
381 ms |
96556 KB |
Output is correct |
29 |
Correct |
382 ms |
96688 KB |
Output is correct |
30 |
Correct |
394 ms |
96676 KB |
Output is correct |
31 |
Correct |
391 ms |
96272 KB |
Output is correct |
32 |
Correct |
382 ms |
96424 KB |
Output is correct |
33 |
Correct |
56 ms |
1620 KB |
Output is correct |
34 |
Correct |
91 ms |
10416 KB |
Output is correct |
35 |
Correct |
357 ms |
96172 KB |
Output is correct |
36 |
Correct |
461 ms |
96444 KB |
Output is correct |
37 |
Correct |
359 ms |
99636 KB |
Output is correct |
38 |
Correct |
959 ms |
194124 KB |
Output is correct |
39 |
Correct |
374 ms |
99108 KB |
Output is correct |
40 |
Correct |
382 ms |
96620 KB |
Output is correct |
41 |
Correct |
392 ms |
97204 KB |
Output is correct |
42 |
Correct |
400 ms |
105528 KB |
Output is correct |
43 |
Correct |
413 ms |
142648 KB |
Output is correct |
44 |
Correct |
48 ms |
1968 KB |
Output is correct |
45 |
Correct |
94 ms |
2036 KB |
Output is correct |
46 |
Correct |
149 ms |
1992 KB |
Output is correct |
47 |
Correct |
211 ms |
2092 KB |
Output is correct |
48 |
Correct |
281 ms |
3308 KB |
Output is correct |
49 |
Correct |
819 ms |
102184 KB |
Output is correct |
50 |
Correct |
853 ms |
102128 KB |
Output is correct |
51 |
Correct |
809 ms |
102392 KB |
Output is correct |
52 |
Correct |
1054 ms |
102456 KB |
Output is correct |
53 |
Correct |
762 ms |
102320 KB |
Output is correct |
54 |
Correct |
733 ms |
102240 KB |
Output is correct |
55 |
Correct |
762 ms |
102192 KB |
Output is correct |
56 |
Correct |
110 ms |
2012 KB |
Output is correct |
57 |
Correct |
244 ms |
2156 KB |
Output is correct |
58 |
Correct |
511 ms |
3156 KB |
Output is correct |
59 |
Correct |
1109 ms |
98348 KB |
Output is correct |
60 |
Correct |
1381 ms |
98444 KB |
Output is correct |
61 |
Correct |
1072 ms |
98360 KB |
Output is correct |
62 |
Correct |
760 ms |
100260 KB |
Output is correct |
63 |
Correct |
1239 ms |
101000 KB |
Output is correct |
64 |
Correct |
1069 ms |
99348 KB |
Output is correct |
65 |
Correct |
1014 ms |
98424 KB |
Output is correct |
66 |
Correct |
1104 ms |
96680 KB |
Output is correct |
67 |
Correct |
1045 ms |
107636 KB |
Output is correct |
68 |
Correct |
879 ms |
127072 KB |
Output is correct |
69 |
Correct |
1435 ms |
145108 KB |
Output is correct |