Submission #3430497
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c<'0' || c>'9'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
ll f=1;
while((c=getchar())!='-' && (c<'0' || c>'9'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=3e5+10,inf=0x3f3f3f3f;
inline bool chkmin(int &x,int y){return (y<x)?(x=y,1):0;}
inline bool chkmax(int &x,int y){return (y>x)?(x=y,1):0;}
int n,w,h;
struct Segment_tree{
int Max[maxn<<2],tag[maxn<<2];
void push_down(int x){
if(tag[x]!=0){
Max[x<<1]+=tag[x],Max[x<<1|1]+=tag[x];
tag[x<<1]+=tag[x],tag[x<<1|1]+=tag[x];
tag[x]=0;
}
}
void build_tree(){
REP(i,1,n<<2) Max[i]=-inf,tag[i]=0;
}
void update(int x,int L,int R,int ql,int qr,int v){
if(ql<=L && R<=qr){
tag[x]+=v;Max[x]+=v;
return;
}
int Mid=(L+R)>>1;push_down(x);
if(ql<=Mid) update(x<<1,L,Mid,ql,qr,v);
if(qr>Mid) update(x<<1|1,Mid+1,R,ql,qr,v);
Max[x]=max(Max[x<<1],Max[x<<1|1]);
}
}Seg;
struct point{
int x,y;
bool operator <(const point &rhs) const{
return x<rhs.x;
}
}a[maxn];
point sta[maxn],stb[maxn];
int tmpa,tmpb,ans;
void work(){
Seg.build_tree();
sort(a+1,a+n+1);
tmpa=tmpb=0;
REP(i,1,n-1){
if(a[i].y<=h/2){
int lst=i;
while(tmpa && a[i].y>=sta[tmpa].y){
Seg.update(1,1,n,sta[tmpa].x,lst-1,sta[tmpa].y-a[i].y);
lst=sta[tmpa].x;--tmpa;
}
if(lst<i) sta[++tmpa]=(point){lst,a[i].y};
}
else{
int lst=i;
while(tmpb && a[i].y<=stb[tmpb].y){
Seg.update(1,1,n,stb[tmpb].x,lst-1,a[i].y-stb[tmpb].y);
lst=stb[tmpb].x,--tmpb;
}
if(lst<i) stb[++tmpb]=(point){lst,a[i].y};
}
sta[++tmpa]=(point){i,0};
stb[++tmpb]=(point){i,h};
Seg.update(1,1,n,i,i,inf+h-a[i].x);
chkmax(ans,Seg.Max[1]+a[i+1].x);
}
}
int main(){
w=read(),h=read(),n=read();
REP(i,1,n) a[i].x=read(),a[i].y=read();
a[++n]=(point){0,0},a[++n]=(point){w,h};
work();
REP(i,1,n) swap(a[i].x,a[i].y);
swap(w,h);
work();
printf("%d\n",ans*2);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
zhou888 |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2427 Byte |
Status |
AC |
Exec Time |
436 ms |
Memory |
15616 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
dia_01.txt, dia_02.txt, dia_03.txt, dia_04.txt, dial_01.txt, dial_02.txt, dial_03.txt, dial_04.txt, dial_05.txt, dial_06.txt, dialr_01.txt, dialr_02.txt, dialr_03.txt, dialr_04.txt, diar_01.txt, diar_02.txt, diar_03.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, poc_t_1.txt, poc_t_2.txt, poc_t_3.txt, poc_t_4.txt, poc_t_5.txt, poc_w_1.txt, poc_w_2.txt, random0_01.txt, random0_02.txt, random0_03.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, rect_01.txt, rect_02.txt, rect_03.txt, rect_04.txt, rect_05.txt, rect_06.txt, rect_07.txt, rect_08.txt, rect_09.txt, rect_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, x_01.txt, x_02.txt, x_03.txt, x_04.txt |
Case Name |
Status |
Exec Time |
Memory |
dia_01.txt |
AC |
431 ms |
15232 KB |
dia_02.txt |
AC |
432 ms |
15232 KB |
dia_03.txt |
AC |
431 ms |
15232 KB |
dia_04.txt |
AC |
436 ms |
15232 KB |
dial_01.txt |
AC |
411 ms |
15232 KB |
dial_02.txt |
AC |
423 ms |
15232 KB |
dial_03.txt |
AC |
415 ms |
15232 KB |
dial_04.txt |
AC |
428 ms |
15232 KB |
dial_05.txt |
AC |
421 ms |
15232 KB |
dial_06.txt |
AC |
420 ms |
15232 KB |
dialr_01.txt |
AC |
387 ms |
14592 KB |
dialr_02.txt |
AC |
390 ms |
14720 KB |
dialr_03.txt |
AC |
388 ms |
14720 KB |
dialr_04.txt |
AC |
388 ms |
14592 KB |
diar_01.txt |
AC |
412 ms |
15104 KB |
diar_02.txt |
AC |
414 ms |
15104 KB |
diar_03.txt |
AC |
416 ms |
15104 KB |
hand_01.txt |
AC |
3 ms |
8448 KB |
hand_02.txt |
AC |
2 ms |
8448 KB |
hand_03.txt |
AC |
2 ms |
8448 KB |
hand_04.txt |
AC |
2 ms |
8448 KB |
hand_05.txt |
AC |
2 ms |
8448 KB |
poc_t_1.txt |
AC |
2 ms |
8448 KB |
poc_t_2.txt |
AC |
2 ms |
8448 KB |
poc_t_3.txt |
AC |
2 ms |
8448 KB |
poc_t_4.txt |
AC |
3 ms |
8448 KB |
poc_t_5.txt |
AC |
3 ms |
8448 KB |
poc_w_1.txt |
AC |
3 ms |
8448 KB |
poc_w_2.txt |
AC |
3 ms |
8448 KB |
random0_01.txt |
AC |
388 ms |
14592 KB |
random0_02.txt |
AC |
388 ms |
14592 KB |
random0_03.txt |
AC |
398 ms |
14592 KB |
random1_01.txt |
AC |
387 ms |
14592 KB |
random1_02.txt |
AC |
388 ms |
14592 KB |
random1_03.txt |
AC |
392 ms |
14592 KB |
random1_04.txt |
AC |
392 ms |
14592 KB |
random1_05.txt |
AC |
396 ms |
14592 KB |
random1_06.txt |
AC |
388 ms |
14592 KB |
random1_07.txt |
AC |
388 ms |
14592 KB |
rect_01.txt |
AC |
400 ms |
14592 KB |
rect_02.txt |
AC |
388 ms |
14720 KB |
rect_03.txt |
AC |
388 ms |
14592 KB |
rect_04.txt |
AC |
368 ms |
15488 KB |
rect_05.txt |
AC |
386 ms |
14720 KB |
rect_06.txt |
AC |
368 ms |
15616 KB |
rect_07.txt |
AC |
388 ms |
14592 KB |
rect_08.txt |
AC |
388 ms |
14720 KB |
rect_09.txt |
AC |
388 ms |
14592 KB |
rect_10.txt |
AC |
388 ms |
14592 KB |
sample_01.txt |
AC |
3 ms |
8448 KB |
sample_02.txt |
AC |
2 ms |
8448 KB |
sample_03.txt |
AC |
2 ms |
8448 KB |
sample_04.txt |
AC |
3 ms |
8448 KB |
x_01.txt |
AC |
329 ms |
15232 KB |
x_02.txt |
AC |
330 ms |
15232 KB |
x_03.txt |
AC |
329 ms |
15232 KB |
x_04.txt |
AC |
334 ms |
15232 KB |