Submission #1693035
Source Code Expand
#include<bits/stdc++.h>
#define N 300005
#define x first
#define y second
using namespace std;
int n,ans,h,w;
pair<int,int> p[N];
const int M=(1<<18)+3;
const int offset=(1<<17)+1;
int addtag[M],mx[M];
void add(int k,int val){
addtag[k]+=val,mx[k]+=val;
}
void update(int k){
while(k!=0){
if((k<<1)<(1<<18)) mx[k]=max(mx[k<<1],mx[k<<1|1])+addtag[k];
k>>=1;
}
}
void pushdown(int k){
if(k!=1) pushdown(k>>1);
if(addtag[k]==0||(k<<1)>=(1<<18)) return;
add(k<<1,addtag[k]),add((k<<1)|1,addtag[k]);
addtag[k]=0;
}
int watch[M];
void modify(int k,int l,int r,int val){//l,r记得加上2^17 区间加
pushdown(l);pushdown(r);
for(int tl=l-1,tr=r+1;(tl^tr)!=1;tl>>=1,tr>>=1){
if((tl&1)==0) add(tl^1,val);
if((tr&1)==1) add(tr^1,val);
}
update(l);update(r);
for(int i=l-offset;i<=r-offset;i++)
watch[i]+=val;
}
int sta1[N],sta2[N],top1,top2;
void solve(){
memset(addtag,0,sizeof(addtag));
memset(mx,0,sizeof(mx));
sort(p+1,p+n+1);p[0].x=0,p[n+1].x=w;
modify(1,0+offset,0+offset,h);
top1=top2=0;sta1[0]=sta2[0]=0;
for(int i=1;i<=n+1;i++){
ans=max(ans,mx[1]+p[i].x);
if(p[i].y*2==h) return;
if(p[i].y*2<h){
modify(1,i+offset,i+offset,h-p[i].x);
modify(1,sta2[top2]+offset,i-1+offset,-p[i].y);
while(top2>0&&p[sta2[top2]].y<=p[i].y){
modify(1,sta2[top2-1]+offset,sta2[top2]-1+offset,-p[i].y+p[sta2[top2]].y);
top2--;
}
sta2[++top2]=i;
}else{
modify(1,i+offset,i+offset,h-p[i].x);
modify(1,sta1[top1]+offset,i-1+offset,p[i].y-h);
while(top1>0&&p[sta1[top1]].y>=p[i].y){
modify(1,sta1[top1-1]+offset,sta1[top1]-1+offset,p[i].y-p[sta1[top1]].y);
top1--;
}
sta1[++top1]=i;
}
}
}
int main(){
scanf("%d%d%d",&w,&h,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
solve();
for(int i=1;i<=n;i++) swap(p[i].x,p[i].y);
swap(h,w);
solve();
cout<<ans*2<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
Wuvin |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1933 Byte |
Status |
WA |
Exec Time |
4203 ms |
Memory |
6528 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&w,&h,&n);
^
./Main.cpp:71:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
^
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
TLE |
4203 ms |
6528 KB |
dia_02.txt |
TLE |
4203 ms |
6528 KB |
dia_03.txt |
TLE |
4203 ms |
6528 KB |
dia_04.txt |
TLE |
4203 ms |
6528 KB |
dial_01.txt |
WA |
83 ms |
6016 KB |
dial_02.txt |
WA |
84 ms |
6016 KB |
dial_03.txt |
AC |
86 ms |
6016 KB |
dial_04.txt |
AC |
88 ms |
6016 KB |
dial_05.txt |
WA |
91 ms |
6016 KB |
dial_06.txt |
WA |
89 ms |
6016 KB |
dialr_01.txt |
WA |
98 ms |
6016 KB |
dialr_02.txt |
WA |
100 ms |
6016 KB |
dialr_03.txt |
WA |
99 ms |
6016 KB |
dialr_04.txt |
WA |
101 ms |
6016 KB |
diar_01.txt |
TLE |
4203 ms |
6528 KB |
diar_02.txt |
TLE |
4203 ms |
6528 KB |
diar_03.txt |
TLE |
4203 ms |
6528 KB |
hand_01.txt |
AC |
3 ms |
4352 KB |
hand_02.txt |
AC |
3 ms |
4352 KB |
hand_03.txt |
AC |
3 ms |
4352 KB |
hand_04.txt |
AC |
3 ms |
4352 KB |
hand_05.txt |
AC |
3 ms |
4352 KB |
poc_t_1.txt |
AC |
3 ms |
4352 KB |
poc_t_2.txt |
AC |
3 ms |
4352 KB |
poc_t_3.txt |
AC |
3 ms |
4352 KB |
poc_t_4.txt |
AC |
3 ms |
4352 KB |
poc_t_5.txt |
AC |
3 ms |
4352 KB |
poc_w_1.txt |
AC |
3 ms |
4352 KB |
poc_w_2.txt |
AC |
3 ms |
4352 KB |
random0_01.txt |
WA |
400 ms |
6016 KB |
random0_02.txt |
WA |
307 ms |
6016 KB |
random0_03.txt |
WA |
521 ms |
6016 KB |
random1_01.txt |
WA |
340 ms |
6016 KB |
random1_02.txt |
WA |
336 ms |
6016 KB |
random1_03.txt |
WA |
520 ms |
6016 KB |
random1_04.txt |
WA |
521 ms |
6016 KB |
random1_05.txt |
WA |
520 ms |
6016 KB |
random1_06.txt |
WA |
530 ms |
6016 KB |
random1_07.txt |
WA |
515 ms |
6016 KB |
rect_01.txt |
WA |
514 ms |
6016 KB |
rect_02.txt |
WA |
516 ms |
6016 KB |
rect_03.txt |
WA |
515 ms |
6016 KB |
rect_04.txt |
WA |
513 ms |
6016 KB |
rect_05.txt |
WA |
344 ms |
6016 KB |
rect_06.txt |
WA |
404 ms |
6016 KB |
rect_07.txt |
WA |
518 ms |
6016 KB |
rect_08.txt |
WA |
517 ms |
6016 KB |
rect_09.txt |
WA |
515 ms |
6016 KB |
rect_10.txt |
WA |
516 ms |
6016 KB |
sample_01.txt |
AC |
3 ms |
4352 KB |
sample_02.txt |
AC |
3 ms |
4352 KB |
sample_03.txt |
AC |
3 ms |
4352 KB |
sample_04.txt |
AC |
3 ms |
4352 KB |
x_01.txt |
TLE |
4203 ms |
6016 KB |
x_02.txt |
TLE |
4203 ms |
6016 KB |
x_03.txt |
TLE |
4203 ms |
6016 KB |
x_04.txt |
TLE |
4203 ms |
6016 KB |