#include "seats.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
int h,w;
int r[1000010];
int c[1000010];
pii arr[1000010];
//segtree
pii sum[8000000];
pii minimo[8000000];
int counter[8000000];
vector<vector<int> >table;
void update_pos(int a, int b){
if(a<0 || a>h-1)return;
if(b<0 || b>w-1)return;
int t[3][3];
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)t[i][j]=1;
}//cout<<a<<" "<<b<<endl;
t[1][1]=0;
if(a==0 || b==0 || table[a-1][b-1]>table[a][b])t[0][0]=0;
if(a==0 || b==w-1 || table[a-1][b+1]>table[a][b])t[0][2]=0;
if(a==h-1 || b==0 || table[a+1][b-1]>table[a][b])t[2][0]=0;
if(a==h-1 || b==w-1 || table[a+1][b+1]>table[a][b])t[2][2]=0;
if(a==0 || table[a-1][b]>table[a][b])t[0][1]=0;
if(b==0 || table[a][b-1]>table[a][b])t[1][0]=0;
if(a==h-1 || table[a+1][b]>table[a][b])t[2][1]=0;
if(b==w-1 || table[a][b+1]>table[a][b])t[1][2]=0;
/*for(int i=0;i<3;i++){
for(int j=0;j<3;j++)cout<<t[i][j];
cout<<endl;
}cout<<endl;*/
int x,y,z,w;
x=t[0][0]+t[0][1]+t[1][0]+t[1][1];
y=t[1][0]+t[1][1]+t[2][0]+t[2][1];
z=t[0][1]+t[0][2]+t[1][1]+t[1][2];
w=t[1][1]+t[1][2]+t[2][1]+t[2][2];
int cnt[5];
for(int i=0;i<5;i++)cnt[i]=0;
cnt[x]++;
cnt[y]++;
cnt[z]++;
cnt[w]++;
//cout<<table[a][b]<<" "<<x<<endl;
//cout<<cnt[0]-cnt[1]<<endl;
arr[table[a][b]].first=cnt[0]-cnt[1];
arr[table[a][b]].second=cnt[2]-cnt[3];
}
pii Sum(pii a, pii b){
pii c=pii(a.first+b.first,a.second+b.second);
return c;
}
pii min(pii a, pii b){
if(a.second<b.second)return a;
if(a.second>b.second)return b;
if(a.first>b.first)return b;
return a;
}
void build(int a, int b, int node){
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
sum[node]=Sum(sum[2*node],sum[2*node+1]);
minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
counter[node]+=counter[2*node+1];
}
}
void update(int a, int b, int node, int pos){
if(pos<a || b<pos)return;
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,pos);
update(mid+1,b,2*node+1,pos);
sum[node]=Sum(sum[2*node],sum[2*node+1]);
minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
counter[node]+=counter[2*node+1];
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
for(int i=0;i<h;i++){
vector<int> a;
for(int j=0;j<w;j++)a.push_back(-1);
table.push_back(a);
}
for(int i=0;i<w*h;i++){
r[i]=R[i];
c[i]=C[i];
table[R[i]][C[i]]=i;
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++)update_pos(i,j);
}
build(0,w*h-1,1);
//for(int i=0;i<h*w;i++)cout<<arr[i].second<<endl;
//cout<<counter[1]<<endl;
}
int swap_seats(int a, int b) {
swap(table[r[a]][c[a]],table[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
for(int i=-1;i<2;i++){
for(int j=-1;j<2;j++){
update_pos(r[a]+i,c[a]+j);
if(r[a]+i>=0 && r[a]+i<=h-1 && c[a]+j>=0 && c[a]+j<=w-1)update(0,h*w-1,1,table[r[a]+i][c[a]+j]);
update_pos(r[b]+i,c[b]+j);
if(r[b]+i>=0 && r[b]+i<=h-1 && c[b]+j>=0 && c[b]+j<=w-1)update(0,h*w-1,1,table[r[b]+i][c[b]+j]);
}
}
//build(0,h*w-1,1);
/*int cnt=0;
int one=0;
int three=0;
for(int i=0;i<h*w;i++){
three+=arr[i].second;
one+=arr[i].first;
if(one==4 && three==0){
cnt++;
}
}*/
return counter[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
504 KB |
Output is correct |
2 |
Correct |
21 ms |
504 KB |
Output is correct |
3 |
Correct |
22 ms |
584 KB |
Output is correct |
4 |
Correct |
11 ms |
772 KB |
Output is correct |
5 |
Correct |
9 ms |
772 KB |
Output is correct |
6 |
Correct |
17 ms |
772 KB |
Output is correct |
7 |
Correct |
22 ms |
772 KB |
Output is correct |
8 |
Correct |
19 ms |
776 KB |
Output is correct |
9 |
Correct |
20 ms |
776 KB |
Output is correct |
10 |
Correct |
63 ms |
776 KB |
Output is correct |
11 |
Correct |
16 ms |
868 KB |
Output is correct |
12 |
Correct |
12 ms |
868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
504 KB |
Output is correct |
2 |
Correct |
21 ms |
504 KB |
Output is correct |
3 |
Correct |
22 ms |
584 KB |
Output is correct |
4 |
Correct |
11 ms |
772 KB |
Output is correct |
5 |
Correct |
9 ms |
772 KB |
Output is correct |
6 |
Correct |
17 ms |
772 KB |
Output is correct |
7 |
Correct |
22 ms |
772 KB |
Output is correct |
8 |
Correct |
19 ms |
776 KB |
Output is correct |
9 |
Correct |
20 ms |
776 KB |
Output is correct |
10 |
Correct |
63 ms |
776 KB |
Output is correct |
11 |
Correct |
16 ms |
868 KB |
Output is correct |
12 |
Correct |
12 ms |
868 KB |
Output is correct |
13 |
Correct |
45 ms |
1684 KB |
Output is correct |
14 |
Correct |
40 ms |
1684 KB |
Output is correct |
15 |
Correct |
18 ms |
1684 KB |
Output is correct |
16 |
Correct |
19 ms |
2220 KB |
Output is correct |
17 |
Correct |
29 ms |
2220 KB |
Output is correct |
18 |
Correct |
44 ms |
2220 KB |
Output is correct |
19 |
Correct |
40 ms |
2220 KB |
Output is correct |
20 |
Correct |
30 ms |
2220 KB |
Output is correct |
21 |
Correct |
18 ms |
2220 KB |
Output is correct |
22 |
Correct |
18 ms |
2280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
584 ms |
76996 KB |
Output is correct |
2 |
Correct |
508 ms |
76996 KB |
Output is correct |
3 |
Correct |
500 ms |
77428 KB |
Output is correct |
4 |
Correct |
461 ms |
77452 KB |
Output is correct |
5 |
Correct |
440 ms |
77452 KB |
Output is correct |
6 |
Correct |
460 ms |
77468 KB |
Output is correct |
7 |
Correct |
491 ms |
78292 KB |
Output is correct |
8 |
Correct |
485 ms |
93756 KB |
Output is correct |
9 |
Correct |
524 ms |
102120 KB |
Output is correct |
10 |
Correct |
472 ms |
102120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
102120 KB |
Output is correct |
2 |
Correct |
98 ms |
102120 KB |
Output is correct |
3 |
Correct |
443 ms |
102120 KB |
Output is correct |
4 |
Correct |
572 ms |
102208 KB |
Output is correct |
5 |
Correct |
429 ms |
102208 KB |
Output is correct |
6 |
Correct |
839 ms |
152800 KB |
Output is correct |
7 |
Correct |
457 ms |
152800 KB |
Output is correct |
8 |
Correct |
545 ms |
152800 KB |
Output is correct |
9 |
Correct |
478 ms |
152800 KB |
Output is correct |
10 |
Correct |
541 ms |
152800 KB |
Output is correct |
11 |
Correct |
588 ms |
152800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
152800 KB |
Output is correct |
2 |
Correct |
51 ms |
152800 KB |
Output is correct |
3 |
Correct |
73 ms |
152800 KB |
Output is correct |
4 |
Correct |
103 ms |
152800 KB |
Output is correct |
5 |
Correct |
140 ms |
152800 KB |
Output is correct |
6 |
Correct |
673 ms |
152800 KB |
Output is correct |
7 |
Correct |
712 ms |
152800 KB |
Output is correct |
8 |
Correct |
669 ms |
152800 KB |
Output is correct |
9 |
Correct |
794 ms |
152800 KB |
Output is correct |
10 |
Correct |
590 ms |
152800 KB |
Output is correct |
11 |
Correct |
570 ms |
152800 KB |
Output is correct |
12 |
Correct |
560 ms |
152800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
504 KB |
Output is correct |
2 |
Correct |
21 ms |
504 KB |
Output is correct |
3 |
Correct |
22 ms |
584 KB |
Output is correct |
4 |
Correct |
11 ms |
772 KB |
Output is correct |
5 |
Correct |
9 ms |
772 KB |
Output is correct |
6 |
Correct |
17 ms |
772 KB |
Output is correct |
7 |
Correct |
22 ms |
772 KB |
Output is correct |
8 |
Correct |
19 ms |
776 KB |
Output is correct |
9 |
Correct |
20 ms |
776 KB |
Output is correct |
10 |
Correct |
63 ms |
776 KB |
Output is correct |
11 |
Correct |
16 ms |
868 KB |
Output is correct |
12 |
Correct |
12 ms |
868 KB |
Output is correct |
13 |
Correct |
45 ms |
1684 KB |
Output is correct |
14 |
Correct |
40 ms |
1684 KB |
Output is correct |
15 |
Correct |
18 ms |
1684 KB |
Output is correct |
16 |
Correct |
19 ms |
2220 KB |
Output is correct |
17 |
Correct |
29 ms |
2220 KB |
Output is correct |
18 |
Correct |
44 ms |
2220 KB |
Output is correct |
19 |
Correct |
40 ms |
2220 KB |
Output is correct |
20 |
Correct |
30 ms |
2220 KB |
Output is correct |
21 |
Correct |
18 ms |
2220 KB |
Output is correct |
22 |
Correct |
18 ms |
2280 KB |
Output is correct |
23 |
Correct |
584 ms |
76996 KB |
Output is correct |
24 |
Correct |
508 ms |
76996 KB |
Output is correct |
25 |
Correct |
500 ms |
77428 KB |
Output is correct |
26 |
Correct |
461 ms |
77452 KB |
Output is correct |
27 |
Correct |
440 ms |
77452 KB |
Output is correct |
28 |
Correct |
460 ms |
77468 KB |
Output is correct |
29 |
Correct |
491 ms |
78292 KB |
Output is correct |
30 |
Correct |
485 ms |
93756 KB |
Output is correct |
31 |
Correct |
524 ms |
102120 KB |
Output is correct |
32 |
Correct |
472 ms |
102120 KB |
Output is correct |
33 |
Correct |
43 ms |
102120 KB |
Output is correct |
34 |
Correct |
98 ms |
102120 KB |
Output is correct |
35 |
Correct |
443 ms |
102120 KB |
Output is correct |
36 |
Correct |
572 ms |
102208 KB |
Output is correct |
37 |
Correct |
429 ms |
102208 KB |
Output is correct |
38 |
Correct |
839 ms |
152800 KB |
Output is correct |
39 |
Correct |
457 ms |
152800 KB |
Output is correct |
40 |
Correct |
545 ms |
152800 KB |
Output is correct |
41 |
Correct |
478 ms |
152800 KB |
Output is correct |
42 |
Correct |
541 ms |
152800 KB |
Output is correct |
43 |
Correct |
588 ms |
152800 KB |
Output is correct |
44 |
Correct |
35 ms |
152800 KB |
Output is correct |
45 |
Correct |
51 ms |
152800 KB |
Output is correct |
46 |
Correct |
73 ms |
152800 KB |
Output is correct |
47 |
Correct |
103 ms |
152800 KB |
Output is correct |
48 |
Correct |
140 ms |
152800 KB |
Output is correct |
49 |
Correct |
673 ms |
152800 KB |
Output is correct |
50 |
Correct |
712 ms |
152800 KB |
Output is correct |
51 |
Correct |
669 ms |
152800 KB |
Output is correct |
52 |
Correct |
794 ms |
152800 KB |
Output is correct |
53 |
Correct |
590 ms |
152800 KB |
Output is correct |
54 |
Correct |
570 ms |
152800 KB |
Output is correct |
55 |
Correct |
560 ms |
152800 KB |
Output is correct |
56 |
Correct |
91 ms |
152800 KB |
Output is correct |
57 |
Correct |
214 ms |
152800 KB |
Output is correct |
58 |
Correct |
361 ms |
152800 KB |
Output is correct |
59 |
Correct |
1117 ms |
152800 KB |
Output is correct |
60 |
Correct |
1514 ms |
152800 KB |
Output is correct |
61 |
Correct |
973 ms |
152800 KB |
Output is correct |
62 |
Correct |
718 ms |
152800 KB |
Output is correct |
63 |
Correct |
1283 ms |
152800 KB |
Output is correct |
64 |
Correct |
1004 ms |
152800 KB |
Output is correct |
65 |
Correct |
931 ms |
152800 KB |
Output is correct |
66 |
Correct |
1112 ms |
152800 KB |
Output is correct |
67 |
Correct |
1057 ms |
152800 KB |
Output is correct |
68 |
Correct |
887 ms |
152800 KB |
Output is correct |
69 |
Correct |
1341 ms |
159340 KB |
Output is correct |