#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];
pii 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];
}
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[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==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[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==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-1,1);
//for(int i=0;i<h*w;i++)cout<<arr[i].second<<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);
update_pos(r[b]+i,c[b]+j);
}
}
/*int pos_a=inv[a];
int pos_b=inv[b];
swap(inv[a],inv[b]);
swap(per[pos_a],per[pos_b]);
update_pos(a);
update(0,w-1,1,a);
update_pos(b);
update(0,w-1,1,b);
if(inv[a]>0){
update_pos(per[inv[a]-1]);
update(0,w-1,1,per[inv[a]-1]);
}
if(inv[a]<w-1){
update_pos(per[inv[a]+1]);
update(0,w-1,1,per[inv[a]+1]);
}
if(inv[b]>0){
update_pos(per[inv[b]-1]);
update(0,w-1,1,per[inv[b]-1]);
}
if(inv[b]<w-1){
update_pos(per[inv[b]+1]);
update(0,w-1,1,per[inv[b]+1]);
}*/
//for(int i=0;i<w;i++)cout<<arr[i]<<endl;
//return counter[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 cnt;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
728 KB |
Output is correct |
3 |
Correct |
10 ms |
728 KB |
Output is correct |
4 |
Correct |
6 ms |
728 KB |
Output is correct |
5 |
Correct |
5 ms |
728 KB |
Output is correct |
6 |
Correct |
7 ms |
868 KB |
Output is correct |
7 |
Correct |
8 ms |
944 KB |
Output is correct |
8 |
Correct |
8 ms |
944 KB |
Output is correct |
9 |
Correct |
8 ms |
944 KB |
Output is correct |
10 |
Correct |
8 ms |
960 KB |
Output is correct |
11 |
Correct |
7 ms |
1036 KB |
Output is correct |
12 |
Correct |
5 ms |
1040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
728 KB |
Output is correct |
3 |
Correct |
10 ms |
728 KB |
Output is correct |
4 |
Correct |
6 ms |
728 KB |
Output is correct |
5 |
Correct |
5 ms |
728 KB |
Output is correct |
6 |
Correct |
7 ms |
868 KB |
Output is correct |
7 |
Correct |
8 ms |
944 KB |
Output is correct |
8 |
Correct |
8 ms |
944 KB |
Output is correct |
9 |
Correct |
8 ms |
944 KB |
Output is correct |
10 |
Correct |
8 ms |
960 KB |
Output is correct |
11 |
Correct |
7 ms |
1036 KB |
Output is correct |
12 |
Correct |
5 ms |
1040 KB |
Output is correct |
13 |
Correct |
73 ms |
1564 KB |
Output is correct |
14 |
Correct |
62 ms |
1564 KB |
Output is correct |
15 |
Correct |
54 ms |
1676 KB |
Output is correct |
16 |
Correct |
76 ms |
2152 KB |
Output is correct |
17 |
Correct |
56 ms |
2152 KB |
Output is correct |
18 |
Correct |
58 ms |
2152 KB |
Output is correct |
19 |
Correct |
79 ms |
2152 KB |
Output is correct |
20 |
Correct |
84 ms |
2304 KB |
Output is correct |
21 |
Correct |
63 ms |
2304 KB |
Output is correct |
22 |
Correct |
92 ms |
2896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4078 ms |
38688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
72 ms |
38688 KB |
Output is correct |
2 |
Correct |
517 ms |
38688 KB |
Output is correct |
3 |
Execution timed out |
4005 ms |
40192 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
40192 KB |
Output is correct |
2 |
Correct |
30 ms |
40192 KB |
Output is correct |
3 |
Correct |
35 ms |
40192 KB |
Output is correct |
4 |
Correct |
84 ms |
40192 KB |
Output is correct |
5 |
Correct |
478 ms |
40192 KB |
Output is correct |
6 |
Execution timed out |
4086 ms |
42044 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
728 KB |
Output is correct |
3 |
Correct |
10 ms |
728 KB |
Output is correct |
4 |
Correct |
6 ms |
728 KB |
Output is correct |
5 |
Correct |
5 ms |
728 KB |
Output is correct |
6 |
Correct |
7 ms |
868 KB |
Output is correct |
7 |
Correct |
8 ms |
944 KB |
Output is correct |
8 |
Correct |
8 ms |
944 KB |
Output is correct |
9 |
Correct |
8 ms |
944 KB |
Output is correct |
10 |
Correct |
8 ms |
960 KB |
Output is correct |
11 |
Correct |
7 ms |
1036 KB |
Output is correct |
12 |
Correct |
5 ms |
1040 KB |
Output is correct |
13 |
Correct |
73 ms |
1564 KB |
Output is correct |
14 |
Correct |
62 ms |
1564 KB |
Output is correct |
15 |
Correct |
54 ms |
1676 KB |
Output is correct |
16 |
Correct |
76 ms |
2152 KB |
Output is correct |
17 |
Correct |
56 ms |
2152 KB |
Output is correct |
18 |
Correct |
58 ms |
2152 KB |
Output is correct |
19 |
Correct |
79 ms |
2152 KB |
Output is correct |
20 |
Correct |
84 ms |
2304 KB |
Output is correct |
21 |
Correct |
63 ms |
2304 KB |
Output is correct |
22 |
Correct |
92 ms |
2896 KB |
Output is correct |
23 |
Execution timed out |
4078 ms |
38688 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |