#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "seats.h"
using namespace std;
const int maxn=1000005;
const int dx[4]={0,0,1,1},dy[4]={0,1,0,1};
int H,W,NUM;
int val[maxn],presum[maxn];
vector<int> R,C;
int S[maxn],T[maxn];
struct node
{
int dta;
int s,cnt;
node *lc,*rc;
void tagdta(const int &c)
{
s+=c;
dta+=c;
}
void downdate()
{
if(dta)
{
if(lc)lc->tagdta(dta);
if(rc)rc->tagdta(dta);
dta=0;
}
}
void update()
{
if(lc->s<rc->s)
{
s=lc->s;
cnt=lc->cnt;
}
else if(rc->s<lc->s)
{
s=rc->s;
cnt=rc->cnt;
}
else
{
s=lc->s;
cnt=lc->cnt+rc->cnt;
}
}
void Add(int l,int r,const int &a,const int &b,const int &c)
{
if(l>=a&&r<=b)
{
tagdta(c);
return;
}
int mid=l+r>>1;
downdate();
if(a<=mid)lc->Add(l,mid,a,b,c);
if(b>mid)rc->Add(mid+1,r,a,b,c);
update();
}
}ndl[maxn*2],*ns=ndl,*root;
node* build(int l,int r)
{
node *x=ns++;
x->dta=0;
if(l==r)
{
x->s=presum[l];
x->cnt=1;
x->lc=x->rc=NULL;
}
else
{
int mid=l+r>>1;
x->lc=build(l,mid);
x->rc=build(mid+1,r);
x->update();
}
return x;
}
int& seat(int *s,const int &x,const int &y)
{
if(x>=0&&x<H&&y>=0&&y<W)return s[x*W+y];
return NUM;
}
const int ValTable[2][3]={
{1,-1,-1},
{1,1,-1}
};
int CalcVal(int *s,const int &x,const int &y,const int w=15)
{
int res=0;
for(int k=0;k<4;k++)
if(w>>k&1)
{
int i=x-1+dx[k];
int j=y-1+dy[k];
int t=seat(s,x,y);
int a=seat(s,i+dx[k^1],j+dy[k^1]);
int b=seat(s,i+dx[k^2],j+dy[k^2]);
int c=seat(s,i+dx[k],j+dy[k]);
res+=ValTable[c<t][(a<t)+(b<t)];
}
//cout<<endl;
return res;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
::H=H;
::W=W;
NUM=H*W;
::R.assign(NUM,0);
::C.assign(NUM,0);
for(int i=0;i<NUM;i++)
{
::R[i]=R[i];
::C[i]=C[i];
seat(S,R[i],C[i])=seat(T,R[i],C[i])=i;
}
for(int i=0;i<NUM;i++)
{
val[i]=CalcVal(S,R[i],C[i]);
if(i==0)presum[i]=val[i];
else presum[i]=presum[i-1]+val[i];
}
//for(int i=0;i<NUM;i++)cout<<val[i]<<' ';cout<<endl;
root=build(0,NUM-1);
}
void UpdateVal(int x,int v)
{
root->Add(0,NUM-1,x,NUM-1,v-val[x]);
val[x]=v;
}
int swap_seats(int a, int b)
{
swap(seat(T,R[a],C[a]),seat(T,R[b],C[b]));
vector<int> p;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
{
int t;
t=seat(T,R[a]+i,C[a]+j);
if(t!=NUM)p.push_back(t);
t=seat(T,R[b]+i,C[b]+j);
if(t!=NUM)p.push_back(t);
}
swap(R[a],R[b]);
swap(C[a],C[b]);
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
for(auto x:p)
{
UpdateVal(x,CalcVal(T,R[x],C[x]));
}
swap(seat(S,R[a],C[a]),seat(S,R[b],C[b]));
if(root->s!=4)return 0;
return root->cnt;
}
Compilation message
seats.cpp: In member function 'void node::Add(int, int, const int&, const int&, const int&)':
seats.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=l+r>>1;
~^~
seats.cpp: In function 'node* build(int, int)':
seats.cpp:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=l+r>>1;
~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
16 ms |
584 KB |
Output is correct |
3 |
Correct |
20 ms |
720 KB |
Output is correct |
4 |
Correct |
10 ms |
720 KB |
Output is correct |
5 |
Correct |
10 ms |
720 KB |
Output is correct |
6 |
Correct |
18 ms |
720 KB |
Output is correct |
7 |
Correct |
18 ms |
720 KB |
Output is correct |
8 |
Correct |
19 ms |
728 KB |
Output is correct |
9 |
Correct |
20 ms |
728 KB |
Output is correct |
10 |
Correct |
18 ms |
728 KB |
Output is correct |
11 |
Correct |
17 ms |
776 KB |
Output is correct |
12 |
Correct |
10 ms |
872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
16 ms |
584 KB |
Output is correct |
3 |
Correct |
20 ms |
720 KB |
Output is correct |
4 |
Correct |
10 ms |
720 KB |
Output is correct |
5 |
Correct |
10 ms |
720 KB |
Output is correct |
6 |
Correct |
18 ms |
720 KB |
Output is correct |
7 |
Correct |
18 ms |
720 KB |
Output is correct |
8 |
Correct |
19 ms |
728 KB |
Output is correct |
9 |
Correct |
20 ms |
728 KB |
Output is correct |
10 |
Correct |
18 ms |
728 KB |
Output is correct |
11 |
Correct |
17 ms |
776 KB |
Output is correct |
12 |
Correct |
10 ms |
872 KB |
Output is correct |
13 |
Correct |
38 ms |
1724 KB |
Output is correct |
14 |
Correct |
41 ms |
1852 KB |
Output is correct |
15 |
Correct |
19 ms |
1852 KB |
Output is correct |
16 |
Correct |
17 ms |
1852 KB |
Output is correct |
17 |
Correct |
28 ms |
1852 KB |
Output is correct |
18 |
Correct |
33 ms |
1852 KB |
Output is correct |
19 |
Correct |
32 ms |
1852 KB |
Output is correct |
20 |
Correct |
25 ms |
1852 KB |
Output is correct |
21 |
Correct |
16 ms |
1852 KB |
Output is correct |
22 |
Correct |
16 ms |
1852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
629 ms |
102492 KB |
Output is correct |
2 |
Correct |
615 ms |
102616 KB |
Output is correct |
3 |
Correct |
515 ms |
102616 KB |
Output is correct |
4 |
Correct |
512 ms |
102616 KB |
Output is correct |
5 |
Correct |
518 ms |
102616 KB |
Output is correct |
6 |
Correct |
503 ms |
102616 KB |
Output is correct |
7 |
Correct |
510 ms |
102616 KB |
Output is correct |
8 |
Correct |
543 ms |
102616 KB |
Output is correct |
9 |
Correct |
527 ms |
102616 KB |
Output is correct |
10 |
Correct |
521 ms |
102616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
102616 KB |
Output is correct |
2 |
Correct |
87 ms |
102616 KB |
Output is correct |
3 |
Correct |
496 ms |
102616 KB |
Output is correct |
4 |
Correct |
681 ms |
102616 KB |
Output is correct |
5 |
Correct |
456 ms |
102616 KB |
Output is correct |
6 |
Correct |
578 ms |
102616 KB |
Output is correct |
7 |
Correct |
507 ms |
102616 KB |
Output is correct |
8 |
Correct |
512 ms |
102616 KB |
Output is correct |
9 |
Correct |
562 ms |
102616 KB |
Output is correct |
10 |
Correct |
497 ms |
102616 KB |
Output is correct |
11 |
Correct |
475 ms |
102616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
102616 KB |
Output is correct |
2 |
Correct |
65 ms |
102616 KB |
Output is correct |
3 |
Correct |
87 ms |
102616 KB |
Output is correct |
4 |
Correct |
99 ms |
102616 KB |
Output is correct |
5 |
Correct |
133 ms |
102616 KB |
Output is correct |
6 |
Correct |
684 ms |
102876 KB |
Output is correct |
7 |
Correct |
718 ms |
102876 KB |
Output is correct |
8 |
Correct |
657 ms |
102920 KB |
Output is correct |
9 |
Correct |
868 ms |
102920 KB |
Output is correct |
10 |
Correct |
606 ms |
102920 KB |
Output is correct |
11 |
Correct |
616 ms |
102920 KB |
Output is correct |
12 |
Correct |
664 ms |
102972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
16 ms |
584 KB |
Output is correct |
3 |
Correct |
20 ms |
720 KB |
Output is correct |
4 |
Correct |
10 ms |
720 KB |
Output is correct |
5 |
Correct |
10 ms |
720 KB |
Output is correct |
6 |
Correct |
18 ms |
720 KB |
Output is correct |
7 |
Correct |
18 ms |
720 KB |
Output is correct |
8 |
Correct |
19 ms |
728 KB |
Output is correct |
9 |
Correct |
20 ms |
728 KB |
Output is correct |
10 |
Correct |
18 ms |
728 KB |
Output is correct |
11 |
Correct |
17 ms |
776 KB |
Output is correct |
12 |
Correct |
10 ms |
872 KB |
Output is correct |
13 |
Correct |
38 ms |
1724 KB |
Output is correct |
14 |
Correct |
41 ms |
1852 KB |
Output is correct |
15 |
Correct |
19 ms |
1852 KB |
Output is correct |
16 |
Correct |
17 ms |
1852 KB |
Output is correct |
17 |
Correct |
28 ms |
1852 KB |
Output is correct |
18 |
Correct |
33 ms |
1852 KB |
Output is correct |
19 |
Correct |
32 ms |
1852 KB |
Output is correct |
20 |
Correct |
25 ms |
1852 KB |
Output is correct |
21 |
Correct |
16 ms |
1852 KB |
Output is correct |
22 |
Correct |
16 ms |
1852 KB |
Output is correct |
23 |
Correct |
629 ms |
102492 KB |
Output is correct |
24 |
Correct |
615 ms |
102616 KB |
Output is correct |
25 |
Correct |
515 ms |
102616 KB |
Output is correct |
26 |
Correct |
512 ms |
102616 KB |
Output is correct |
27 |
Correct |
518 ms |
102616 KB |
Output is correct |
28 |
Correct |
503 ms |
102616 KB |
Output is correct |
29 |
Correct |
510 ms |
102616 KB |
Output is correct |
30 |
Correct |
543 ms |
102616 KB |
Output is correct |
31 |
Correct |
527 ms |
102616 KB |
Output is correct |
32 |
Correct |
521 ms |
102616 KB |
Output is correct |
33 |
Correct |
38 ms |
102616 KB |
Output is correct |
34 |
Correct |
87 ms |
102616 KB |
Output is correct |
35 |
Correct |
496 ms |
102616 KB |
Output is correct |
36 |
Correct |
681 ms |
102616 KB |
Output is correct |
37 |
Correct |
456 ms |
102616 KB |
Output is correct |
38 |
Correct |
578 ms |
102616 KB |
Output is correct |
39 |
Correct |
507 ms |
102616 KB |
Output is correct |
40 |
Correct |
512 ms |
102616 KB |
Output is correct |
41 |
Correct |
562 ms |
102616 KB |
Output is correct |
42 |
Correct |
497 ms |
102616 KB |
Output is correct |
43 |
Correct |
475 ms |
102616 KB |
Output is correct |
44 |
Correct |
45 ms |
102616 KB |
Output is correct |
45 |
Correct |
65 ms |
102616 KB |
Output is correct |
46 |
Correct |
87 ms |
102616 KB |
Output is correct |
47 |
Correct |
99 ms |
102616 KB |
Output is correct |
48 |
Correct |
133 ms |
102616 KB |
Output is correct |
49 |
Correct |
684 ms |
102876 KB |
Output is correct |
50 |
Correct |
718 ms |
102876 KB |
Output is correct |
51 |
Correct |
657 ms |
102920 KB |
Output is correct |
52 |
Correct |
868 ms |
102920 KB |
Output is correct |
53 |
Correct |
606 ms |
102920 KB |
Output is correct |
54 |
Correct |
616 ms |
102920 KB |
Output is correct |
55 |
Correct |
664 ms |
102972 KB |
Output is correct |
56 |
Correct |
99 ms |
102972 KB |
Output is correct |
57 |
Correct |
174 ms |
102972 KB |
Output is correct |
58 |
Correct |
308 ms |
102972 KB |
Output is correct |
59 |
Correct |
1212 ms |
102972 KB |
Output is correct |
60 |
Correct |
1618 ms |
102972 KB |
Output is correct |
61 |
Correct |
967 ms |
102972 KB |
Output is correct |
62 |
Correct |
767 ms |
102972 KB |
Output is correct |
63 |
Correct |
1318 ms |
102972 KB |
Output is correct |
64 |
Correct |
1050 ms |
102972 KB |
Output is correct |
65 |
Correct |
959 ms |
102972 KB |
Output is correct |
66 |
Correct |
1145 ms |
102972 KB |
Output is correct |
67 |
Correct |
1045 ms |
102972 KB |
Output is correct |
68 |
Correct |
825 ms |
102972 KB |
Output is correct |
69 |
Correct |
1209 ms |
102972 KB |
Output is correct |