#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=1000050;
const int M=2*N;
const int inf=2e6;
int ls[M],rs[M],cnt[M],root,tsz,n;
ll mn[M],lzy[M],val[N];
void Build(int &c, int ss, int se)
{
c=++tsz;mn[c]=lzy[c]=0;cnt[c]=se-ss+1;
if(ss==se){ mn[c]=val[ss];return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
mn[c]=min(mn[ls[c]],mn[rs[c]]);
cnt[c]=0;
if(mn[c]==mn[ls[c]]) cnt[c]+=cnt[ls[c]];
if(mn[c]==mn[rs[c]]) cnt[c]+=cnt[rs[c]];
}
void Push(int c, int ss, int se)
{
if(!lzy[c]) return;
if(ss!=se)
{
lzy[ls[c]]+=lzy[c];mn[ls[c]]+=lzy[c];
lzy[rs[c]]+=lzy[c];mn[rs[c]]+=lzy[c];
}
lzy[c]=0;
}
void Inc(int c, int ss, int se, int qs, int qe, int f)
{
if(qs>se || ss>qe || qs>qe) return;
if(qs<=ss && qe>=se){ lzy[c]+=f;mn[c]+=f;return;}
int mid=ss+se>>1;
Push(c,ss,se);
Inc(ls[c],ss,mid,qs,qe,f);
Inc(rs[c],mid+1,se,qs,qe,f);
mn[c]=min(mn[ls[c]],mn[rs[c]]);
cnt[c]=0;
if(mn[c]==mn[ls[c]]) cnt[c]+=cnt[ls[c]];
if(mn[c]==mn[rs[c]]) cnt[c]+=cnt[rs[c]];
}
int Get(){ return cnt[root]*(mn[root]==4);}
vector<vector<int> > matrix,add;
int x[N],y[N];
void Add(int x, int y, int f)
{
if(add[x][y]+f>1 || add[x][y]+f<0) return;
add[x][y]+=f;
vector<int> v={matrix[x][y],matrix[x+1][y],matrix[x][y+1],matrix[x+1][y+1]};
sort(v.begin(),v.end());
Inc(root,0,n-1,v[0],v[1]-1,f);
Inc(root,0,n-1,v[2],v[3]-1,f*inf);
}
ll inc[N];
void Put(int x, int y, int f)
{
if(add[x][y]+f>1 || add[x][y]+f<0) return;
add[x][y]+=f;
vector<int> v={matrix[x][y],matrix[x+1][y],matrix[x][y+1],matrix[x+1][y+1]};
sort(v.begin(),v.end());
//Inc(root,0,n-1,v[0],v[1]-1,f);
//Inc(root,0,n-1,v[2],v[3]-1,f*inf);
inc[v[0]]+=f;inc[v[1]]-=f;
inc[v[2]]+=f*inf;inc[v[3]]-=f*inf;
}
void Solve(int n)
{
ll tmp=0;
for(int i=0;i<n;i++) tmp+=inc[i],val[i]=tmp;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n=H*W;
matrix.resize(H+2);for(int i=0;i<matrix.size();i++) matrix[i].resize(W+2);
add.resize(H+2);for(int i=0;i<add.size();i++) add[i].resize(W+2);
for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
for(int i=0;i<n;i++) x[i]=R[i]+1,y[i]=C[i]+1,matrix[x[i]][y[i]]=i;
for(int i=0;i<=H;i++) for(int j=0;j<=W;j++) Put(i,j,1);
Solve(n);
Build(root,0,n-1);
}
void AddPt(int x, int y, int f)
{
Add(x-1,y-1,f);
Add(x-1,y,f);
Add(x,y-1,f);
Add(x,y,f);
}
int swap_seats(int a, int b)
{
AddPt(x[a],y[a],-1);
AddPt(x[b],y[b],-1);
swap(matrix[x[a]][y[a]],matrix[x[b]][y[b]]);
swap(x[a],x[b]);
swap(y[a],y[b]);
AddPt(x[a],y[a],1);
AddPt(x[b],y[b],1);
return Get();
}
/*int BruteForce(int H, int W, vector<int> R, vector<int> C)
{
int n=H*W;
int xl=n,xr=-1,yl=n,yr=-1,ans=0;
for(int i=0;i<n;i++)
{
xl=min(xl,R[i]);
xr=max(xr,R[i]);
yl=min(yl,C[i]);
yr=max(yr,C[i]);
if(i+1==(xr-xl+1)*(yr-yl+1)) ans++;
}
return ans;
}
void StressTest()
{
srand(time(0));
int t=1000;
while(t--)
{
int n=rand()%1000+1;
vector<int> R,C;R.resize(n);C.resize(n);
for(int i=0;i<n;i++) C[i]=i;
random_shuffle(C.begin(),C.end());
give_initial_chart(1,n,R,C);
int sol=Get(),ans=BruteForce(1,n,R,C);
if(sol!=ans)
{
printf("%i\n",n);
for(int i=0;i<n;i++) printf("%i ",C[i]);printf("\n");
printf("my:%i brute:%i\n",sol,ans);
return;
}
}
printf("OK\n");
}
int main()
{
StressTest();
return 0;
}*/
Compilation message
seats.cpp: In function 'void Build(int&, int, int)':
seats.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
seats.cpp: In function 'void Inc(int, int, int, int, int, int)':
seats.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:78:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
matrix.resize(H+2);for(int i=0;i<matrix.size();i++) matrix[i].resize(W+2);
~^~~~~~~~~~~~~~
seats.cpp:79:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
add.resize(H+2);for(int i=0;i<add.size();i++) add[i].resize(W+2);
~^~~~~~~~~~~
seats.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
~^~~~~~~~~~~~~~
seats.cpp:80:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
596 KB |
Output is correct |
3 |
Correct |
35 ms |
632 KB |
Output is correct |
4 |
Correct |
23 ms |
612 KB |
Output is correct |
5 |
Correct |
19 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
512 KB |
Output is correct |
7 |
Correct |
32 ms |
632 KB |
Output is correct |
8 |
Correct |
29 ms |
632 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
39 ms |
640 KB |
Output is correct |
11 |
Correct |
30 ms |
640 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
596 KB |
Output is correct |
3 |
Correct |
35 ms |
632 KB |
Output is correct |
4 |
Correct |
23 ms |
612 KB |
Output is correct |
5 |
Correct |
19 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
512 KB |
Output is correct |
7 |
Correct |
32 ms |
632 KB |
Output is correct |
8 |
Correct |
29 ms |
632 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
39 ms |
640 KB |
Output is correct |
11 |
Correct |
30 ms |
640 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
13 |
Correct |
74 ms |
1648 KB |
Output is correct |
14 |
Correct |
84 ms |
1664 KB |
Output is correct |
15 |
Correct |
50 ms |
1792 KB |
Output is correct |
16 |
Correct |
42 ms |
2684 KB |
Output is correct |
17 |
Correct |
57 ms |
1784 KB |
Output is correct |
18 |
Correct |
57 ms |
1784 KB |
Output is correct |
19 |
Correct |
54 ms |
1784 KB |
Output is correct |
20 |
Correct |
47 ms |
2168 KB |
Output is correct |
21 |
Correct |
34 ms |
1792 KB |
Output is correct |
22 |
Correct |
37 ms |
2724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
816 ms |
115896 KB |
Output is correct |
2 |
Correct |
551 ms |
111128 KB |
Output is correct |
3 |
Correct |
566 ms |
110532 KB |
Output is correct |
4 |
Correct |
507 ms |
110584 KB |
Output is correct |
5 |
Correct |
529 ms |
110584 KB |
Output is correct |
6 |
Correct |
534 ms |
110596 KB |
Output is correct |
7 |
Correct |
538 ms |
110716 KB |
Output is correct |
8 |
Correct |
568 ms |
110584 KB |
Output is correct |
9 |
Correct |
536 ms |
110584 KB |
Output is correct |
10 |
Correct |
493 ms |
110660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
1664 KB |
Output is correct |
2 |
Correct |
141 ms |
10872 KB |
Output is correct |
3 |
Correct |
478 ms |
110356 KB |
Output is correct |
4 |
Correct |
858 ms |
110200 KB |
Output is correct |
5 |
Correct |
560 ms |
126212 KB |
Output is correct |
6 |
Correct |
1262 ms |
212348 KB |
Output is correct |
7 |
Correct |
478 ms |
115832 KB |
Output is correct |
8 |
Correct |
494 ms |
110712 KB |
Output is correct |
9 |
Correct |
523 ms |
111224 KB |
Output is correct |
10 |
Correct |
512 ms |
119792 KB |
Output is correct |
11 |
Correct |
549 ms |
157552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
2112 KB |
Output is correct |
2 |
Correct |
120 ms |
2056 KB |
Output is correct |
3 |
Correct |
240 ms |
2288 KB |
Output is correct |
4 |
Correct |
224 ms |
2292 KB |
Output is correct |
5 |
Correct |
379 ms |
3404 KB |
Output is correct |
6 |
Correct |
1106 ms |
118392 KB |
Output is correct |
7 |
Correct |
1232 ms |
121016 KB |
Output is correct |
8 |
Correct |
1091 ms |
120140 KB |
Output is correct |
9 |
Correct |
1770 ms |
121844 KB |
Output is correct |
10 |
Correct |
929 ms |
121724 KB |
Output is correct |
11 |
Correct |
955 ms |
121696 KB |
Output is correct |
12 |
Correct |
936 ms |
121768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
512 KB |
Output is correct |
2 |
Correct |
25 ms |
596 KB |
Output is correct |
3 |
Correct |
35 ms |
632 KB |
Output is correct |
4 |
Correct |
23 ms |
612 KB |
Output is correct |
5 |
Correct |
19 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
512 KB |
Output is correct |
7 |
Correct |
32 ms |
632 KB |
Output is correct |
8 |
Correct |
29 ms |
632 KB |
Output is correct |
9 |
Correct |
36 ms |
512 KB |
Output is correct |
10 |
Correct |
39 ms |
640 KB |
Output is correct |
11 |
Correct |
30 ms |
640 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
13 |
Correct |
74 ms |
1648 KB |
Output is correct |
14 |
Correct |
84 ms |
1664 KB |
Output is correct |
15 |
Correct |
50 ms |
1792 KB |
Output is correct |
16 |
Correct |
42 ms |
2684 KB |
Output is correct |
17 |
Correct |
57 ms |
1784 KB |
Output is correct |
18 |
Correct |
57 ms |
1784 KB |
Output is correct |
19 |
Correct |
54 ms |
1784 KB |
Output is correct |
20 |
Correct |
47 ms |
2168 KB |
Output is correct |
21 |
Correct |
34 ms |
1792 KB |
Output is correct |
22 |
Correct |
37 ms |
2724 KB |
Output is correct |
23 |
Correct |
816 ms |
115896 KB |
Output is correct |
24 |
Correct |
551 ms |
111128 KB |
Output is correct |
25 |
Correct |
566 ms |
110532 KB |
Output is correct |
26 |
Correct |
507 ms |
110584 KB |
Output is correct |
27 |
Correct |
529 ms |
110584 KB |
Output is correct |
28 |
Correct |
534 ms |
110596 KB |
Output is correct |
29 |
Correct |
538 ms |
110716 KB |
Output is correct |
30 |
Correct |
568 ms |
110584 KB |
Output is correct |
31 |
Correct |
536 ms |
110584 KB |
Output is correct |
32 |
Correct |
493 ms |
110660 KB |
Output is correct |
33 |
Correct |
80 ms |
1664 KB |
Output is correct |
34 |
Correct |
141 ms |
10872 KB |
Output is correct |
35 |
Correct |
478 ms |
110356 KB |
Output is correct |
36 |
Correct |
858 ms |
110200 KB |
Output is correct |
37 |
Correct |
560 ms |
126212 KB |
Output is correct |
38 |
Correct |
1262 ms |
212348 KB |
Output is correct |
39 |
Correct |
478 ms |
115832 KB |
Output is correct |
40 |
Correct |
494 ms |
110712 KB |
Output is correct |
41 |
Correct |
523 ms |
111224 KB |
Output is correct |
42 |
Correct |
512 ms |
119792 KB |
Output is correct |
43 |
Correct |
549 ms |
157552 KB |
Output is correct |
44 |
Correct |
70 ms |
2112 KB |
Output is correct |
45 |
Correct |
120 ms |
2056 KB |
Output is correct |
46 |
Correct |
240 ms |
2288 KB |
Output is correct |
47 |
Correct |
224 ms |
2292 KB |
Output is correct |
48 |
Correct |
379 ms |
3404 KB |
Output is correct |
49 |
Correct |
1106 ms |
118392 KB |
Output is correct |
50 |
Correct |
1232 ms |
121016 KB |
Output is correct |
51 |
Correct |
1091 ms |
120140 KB |
Output is correct |
52 |
Correct |
1770 ms |
121844 KB |
Output is correct |
53 |
Correct |
929 ms |
121724 KB |
Output is correct |
54 |
Correct |
955 ms |
121696 KB |
Output is correct |
55 |
Correct |
936 ms |
121768 KB |
Output is correct |
56 |
Correct |
137 ms |
2148 KB |
Output is correct |
57 |
Correct |
308 ms |
2136 KB |
Output is correct |
58 |
Correct |
518 ms |
3176 KB |
Output is correct |
59 |
Correct |
1846 ms |
106328 KB |
Output is correct |
60 |
Correct |
2924 ms |
106264 KB |
Output is correct |
61 |
Correct |
1279 ms |
106360 KB |
Output is correct |
62 |
Correct |
1176 ms |
114296 KB |
Output is correct |
63 |
Correct |
2449 ms |
111440 KB |
Output is correct |
64 |
Correct |
1577 ms |
106740 KB |
Output is correct |
65 |
Correct |
1422 ms |
106328 KB |
Output is correct |
66 |
Correct |
1869 ms |
106872 KB |
Output is correct |
67 |
Correct |
1725 ms |
115588 KB |
Output is correct |
68 |
Correct |
1253 ms |
135108 KB |
Output is correct |
69 |
Correct |
2766 ms |
153300 KB |
Output is correct |