#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int SZ=1<<20, dx[]={-1,0,1,0}, dy[]={0,-1,0,1};
vector<pair<int,int>> P;
pair<int,int> tree[2*SZ], lazy[2*SZ];
int N, M, tcnt[2*SZ], idx[1000000];
void lazy_propagation(int bit, int s, int e)
{
tree[bit].first+=lazy[bit].first;
tree[bit].second+=lazy[bit].second;
if(s<e) {
lazy[2*bit].first+=lazy[bit].first;
lazy[2*bit].second+=lazy[bit].second;
lazy[2*bit+1].first+=lazy[bit].first;
lazy[2*bit+1].second+=lazy[bit].second;
}
lazy[bit]={0,0};
}
void add_tree(int n, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(e<n) return;
if(n<=s) {
tree[bit].first+=v.first;
tree[bit].second+=v.second;
if(s<e) {
lazy[2*bit].first+=v.first;
lazy[2*bit].second+=v.second;
lazy[2*bit+1].first+=v.first;
lazy[2*bit+1].second+=v.second;
}
return;
}
add_tree(n,v,2*bit,s,m);
add_tree(n,v,2*bit+1,m+1,e);
tree[bit]=min(tree[2*bit],tree[2*bit+1]);
tcnt[bit]=(tree[bit]==tree[2*bit] ? tcnt[2*bit]:0)+(tree[bit]==tree[2*bit+1] ? tcnt[2*bit+1]:0);
}
bool valid_coord(int x, int y)
{
return 0<=x && x<N && 0<=y && y<M;
}
int &convert(int x, int y)
{
return idx[x*M+y];
}
pair<int,int> get_corner(int x, int y, int i)
{
pair<int,int> ret;
for(int k=0;k<4;k++) {
if(valid_coord(x+dx[k],y+dy[k]) && valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) && convert(x+dx[k],y+dy[k])<=i && convert(x+dx[(k+1)&3],y+dy[(k+1)&3])<=i && convert(x,y)>i) {
ret.second++;
}
else if((!valid_coord(x+dx[k],y+dy[k]) || convert(x+dx[k],y+dy[k])>i) && (!valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) || convert(x+dx[(k+1)&3],y+dy[(k+1)&3])>i) && convert(x,y)<=i) {
ret.first++;
}
}
return ret;
}
pair<int,int> get_diff(int i)
{
pair<int,int> ret, temp;
int x=P[i].first, y=P[i].second;
temp=get_corner(x,y,i); ret.first+=temp.first; ret.second+=temp.second;
temp=get_corner(x,y,i-1); ret.first-=temp.first; ret.second-=temp.second;
for(int k=0;k<4;k++) if(valid_coord(x+dx[k],y+dy[k])) {
temp=get_corner(x+dx[k],y+dy[k],i); ret.first+=temp.first; ret.second+=temp.second;
temp=get_corner(x+dx[k],y+dy[k],i-1); ret.first-=temp.first; ret.second-=temp.second;
}
return ret;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
P.resize(H*W);
N=H; M=W;
for(int i=0;i<H*W;i++) {
P[i]={R[i],C[i]};
convert(R[i],C[i])=i;
tcnt[SZ+i]=1;
}
tree[SZ]=get_diff(0);
for(int i=1;i<H*W;i++) {
tree[SZ+i]=get_diff(i);
tree[SZ+i].first+=tree[SZ+i-1].first;
tree[SZ+i].second+=tree[SZ+i-1].second;
}
for(int i=H*W;i<SZ;i++) tree[SZ+i]=make_pair(0x1fffffff,0x1fffffff);
for(int i=SZ-1;i;i--) {
tree[i]=min(tree[2*i],tree[2*i+1]);
tcnt[i]=(tree[i]==tree[2*i] ? tcnt[2*i]:0)+(tree[i]==tree[2*i+1] ? tcnt[2*i+1]:0);
}
}
int swap_seats(int a, int b)
{
pair<int,int> temp;
int x1=P[a].first, y1=P[a].second, x2=P[b].first, y2=P[b].second;
set<int> C;
for(int dx=-1;dx<2;dx++) for(int dy=-1;dy<2;dy++) {
if(valid_coord(x1+dx,y1+dy) && 1LL*(convert(x1+dx,y1+dy)-a)*(convert(x1+dx,y1+dy)-b)<=0) C.insert(convert(x1+dx,y1+dy));
if(valid_coord(x2+dx,y2+dy) && 1LL*(convert(x2+dx,y2+dy)-a)*(convert(x2+dx,y2+dy)-b)<=0) C.insert(convert(x2+dx,y2+dy));
}
for(auto c: C) {
temp=get_diff(c); temp.first*=-1; temp.second*=-1;
add_tree(c,temp);
}
swap(P[a],P[b]);
swap(convert(P[a].first,P[a].second),convert(P[b].first,P[b].second));
for(auto c: C) add_tree(c,get_diff(c));
return tcnt[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
21112 KB |
Output is correct |
2 |
Correct |
88 ms |
21112 KB |
Output is correct |
3 |
Correct |
85 ms |
21112 KB |
Output is correct |
4 |
Correct |
51 ms |
21112 KB |
Output is correct |
5 |
Correct |
55 ms |
21084 KB |
Output is correct |
6 |
Correct |
61 ms |
21112 KB |
Output is correct |
7 |
Correct |
106 ms |
21100 KB |
Output is correct |
8 |
Correct |
112 ms |
21084 KB |
Output is correct |
9 |
Correct |
94 ms |
21112 KB |
Output is correct |
10 |
Correct |
84 ms |
21112 KB |
Output is correct |
11 |
Correct |
82 ms |
21148 KB |
Output is correct |
12 |
Correct |
56 ms |
21108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
21112 KB |
Output is correct |
2 |
Correct |
88 ms |
21112 KB |
Output is correct |
3 |
Correct |
85 ms |
21112 KB |
Output is correct |
4 |
Correct |
51 ms |
21112 KB |
Output is correct |
5 |
Correct |
55 ms |
21084 KB |
Output is correct |
6 |
Correct |
61 ms |
21112 KB |
Output is correct |
7 |
Correct |
106 ms |
21100 KB |
Output is correct |
8 |
Correct |
112 ms |
21084 KB |
Output is correct |
9 |
Correct |
94 ms |
21112 KB |
Output is correct |
10 |
Correct |
84 ms |
21112 KB |
Output is correct |
11 |
Correct |
82 ms |
21148 KB |
Output is correct |
12 |
Correct |
56 ms |
21108 KB |
Output is correct |
13 |
Correct |
109 ms |
21640 KB |
Output is correct |
14 |
Correct |
91 ms |
21608 KB |
Output is correct |
15 |
Correct |
55 ms |
21668 KB |
Output is correct |
16 |
Correct |
61 ms |
21624 KB |
Output is correct |
17 |
Correct |
85 ms |
21624 KB |
Output is correct |
18 |
Correct |
108 ms |
21668 KB |
Output is correct |
19 |
Correct |
107 ms |
21624 KB |
Output is correct |
20 |
Correct |
73 ms |
21624 KB |
Output is correct |
21 |
Correct |
54 ms |
21624 KB |
Output is correct |
22 |
Correct |
57 ms |
21624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1116 ms |
60516 KB |
Output is correct |
2 |
Correct |
783 ms |
60388 KB |
Output is correct |
3 |
Correct |
638 ms |
60260 KB |
Output is correct |
4 |
Correct |
652 ms |
60392 KB |
Output is correct |
5 |
Correct |
642 ms |
60516 KB |
Output is correct |
6 |
Correct |
631 ms |
60304 KB |
Output is correct |
7 |
Correct |
718 ms |
60396 KB |
Output is correct |
8 |
Correct |
661 ms |
60260 KB |
Output is correct |
9 |
Correct |
666 ms |
60388 KB |
Output is correct |
10 |
Correct |
744 ms |
60064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
21612 KB |
Output is correct |
2 |
Correct |
173 ms |
24784 KB |
Output is correct |
3 |
Correct |
742 ms |
60004 KB |
Output is correct |
4 |
Correct |
1064 ms |
60204 KB |
Output is correct |
5 |
Correct |
495 ms |
59736 KB |
Output is correct |
6 |
Correct |
707 ms |
60032 KB |
Output is correct |
7 |
Correct |
715 ms |
60232 KB |
Output is correct |
8 |
Correct |
773 ms |
60316 KB |
Output is correct |
9 |
Correct |
656 ms |
60256 KB |
Output is correct |
10 |
Correct |
673 ms |
60388 KB |
Output is correct |
11 |
Correct |
507 ms |
59520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
22260 KB |
Output is correct |
2 |
Correct |
252 ms |
22188 KB |
Output is correct |
3 |
Correct |
287 ms |
22260 KB |
Output is correct |
4 |
Correct |
320 ms |
22304 KB |
Output is correct |
5 |
Correct |
266 ms |
22540 KB |
Output is correct |
6 |
Correct |
899 ms |
61320 KB |
Output is correct |
7 |
Correct |
930 ms |
61376 KB |
Output is correct |
8 |
Correct |
833 ms |
61352 KB |
Output is correct |
9 |
Correct |
892 ms |
61440 KB |
Output is correct |
10 |
Correct |
684 ms |
61304 KB |
Output is correct |
11 |
Correct |
733 ms |
61416 KB |
Output is correct |
12 |
Correct |
685 ms |
61424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
21112 KB |
Output is correct |
2 |
Correct |
88 ms |
21112 KB |
Output is correct |
3 |
Correct |
85 ms |
21112 KB |
Output is correct |
4 |
Correct |
51 ms |
21112 KB |
Output is correct |
5 |
Correct |
55 ms |
21084 KB |
Output is correct |
6 |
Correct |
61 ms |
21112 KB |
Output is correct |
7 |
Correct |
106 ms |
21100 KB |
Output is correct |
8 |
Correct |
112 ms |
21084 KB |
Output is correct |
9 |
Correct |
94 ms |
21112 KB |
Output is correct |
10 |
Correct |
84 ms |
21112 KB |
Output is correct |
11 |
Correct |
82 ms |
21148 KB |
Output is correct |
12 |
Correct |
56 ms |
21108 KB |
Output is correct |
13 |
Correct |
109 ms |
21640 KB |
Output is correct |
14 |
Correct |
91 ms |
21608 KB |
Output is correct |
15 |
Correct |
55 ms |
21668 KB |
Output is correct |
16 |
Correct |
61 ms |
21624 KB |
Output is correct |
17 |
Correct |
85 ms |
21624 KB |
Output is correct |
18 |
Correct |
108 ms |
21668 KB |
Output is correct |
19 |
Correct |
107 ms |
21624 KB |
Output is correct |
20 |
Correct |
73 ms |
21624 KB |
Output is correct |
21 |
Correct |
54 ms |
21624 KB |
Output is correct |
22 |
Correct |
57 ms |
21624 KB |
Output is correct |
23 |
Correct |
1116 ms |
60516 KB |
Output is correct |
24 |
Correct |
783 ms |
60388 KB |
Output is correct |
25 |
Correct |
638 ms |
60260 KB |
Output is correct |
26 |
Correct |
652 ms |
60392 KB |
Output is correct |
27 |
Correct |
642 ms |
60516 KB |
Output is correct |
28 |
Correct |
631 ms |
60304 KB |
Output is correct |
29 |
Correct |
718 ms |
60396 KB |
Output is correct |
30 |
Correct |
661 ms |
60260 KB |
Output is correct |
31 |
Correct |
666 ms |
60388 KB |
Output is correct |
32 |
Correct |
744 ms |
60064 KB |
Output is correct |
33 |
Correct |
125 ms |
21612 KB |
Output is correct |
34 |
Correct |
173 ms |
24784 KB |
Output is correct |
35 |
Correct |
742 ms |
60004 KB |
Output is correct |
36 |
Correct |
1064 ms |
60204 KB |
Output is correct |
37 |
Correct |
495 ms |
59736 KB |
Output is correct |
38 |
Correct |
707 ms |
60032 KB |
Output is correct |
39 |
Correct |
715 ms |
60232 KB |
Output is correct |
40 |
Correct |
773 ms |
60316 KB |
Output is correct |
41 |
Correct |
656 ms |
60256 KB |
Output is correct |
42 |
Correct |
673 ms |
60388 KB |
Output is correct |
43 |
Correct |
507 ms |
59520 KB |
Output is correct |
44 |
Correct |
159 ms |
22260 KB |
Output is correct |
45 |
Correct |
252 ms |
22188 KB |
Output is correct |
46 |
Correct |
287 ms |
22260 KB |
Output is correct |
47 |
Correct |
320 ms |
22304 KB |
Output is correct |
48 |
Correct |
266 ms |
22540 KB |
Output is correct |
49 |
Correct |
899 ms |
61320 KB |
Output is correct |
50 |
Correct |
930 ms |
61376 KB |
Output is correct |
51 |
Correct |
833 ms |
61352 KB |
Output is correct |
52 |
Correct |
892 ms |
61440 KB |
Output is correct |
53 |
Correct |
684 ms |
61304 KB |
Output is correct |
54 |
Correct |
733 ms |
61416 KB |
Output is correct |
55 |
Correct |
685 ms |
61424 KB |
Output is correct |
56 |
Correct |
372 ms |
22212 KB |
Output is correct |
57 |
Correct |
673 ms |
22260 KB |
Output is correct |
58 |
Correct |
916 ms |
22840 KB |
Output is correct |
59 |
Correct |
1907 ms |
61392 KB |
Output is correct |
60 |
Correct |
2354 ms |
61404 KB |
Output is correct |
61 |
Correct |
1676 ms |
61412 KB |
Output is correct |
62 |
Correct |
970 ms |
61288 KB |
Output is correct |
63 |
Correct |
1898 ms |
61380 KB |
Output is correct |
64 |
Correct |
1721 ms |
61412 KB |
Output is correct |
65 |
Correct |
1529 ms |
61284 KB |
Output is correct |
66 |
Correct |
1903 ms |
61412 KB |
Output is correct |
67 |
Correct |
1692 ms |
61412 KB |
Output is correct |
68 |
Correct |
1140 ms |
61328 KB |
Output is correct |
69 |
Correct |
1662 ms |
61532 KB |
Output is correct |