Submission #1690916
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define L(__) (__ << 1)
#define R(__) (L(__)|1)
#define LL long long
#define oo (1<<30)
#define N 300005
using namespace std;
int st1[N],top1,st2[N],top2;
int n,w,h,m,z[N],ans,A[4*N],add[4*N];
struct dot{
int x,y;
dot(int _x=0,int _y=0){ x=_x,y=_y;}
}a[N],b[N];
bool cmp(const dot &p,const dot &q){ return p.x<q.x||(p.x==q.x&&p.y<q.y);}
int map(int x){ return lower_bound(z+1,z+m+1,x)-z;}
void update(int t){ A[t]=max(A[L(t)],A[R(t)]);}
void build(int t,int l,int r)
{
int mid=(l+r)>>1; add[t]=0;
if(l==r){ A[t]=-z[l]; return ;}
build(L(t),l,mid);
build(R(t),mid+1,r);
update(t);
}
void Add(int t,int d){ add[t]+=d,A[t]+=d;}
void push(int t)
{
if(add[t]==0) return ;
Add(L(t),add[t]);
Add(R(t),add[t]);
add[t]=0;
}
void modify(int t,int l,int r,int l1,int r1,int d)
{
int mid=(l+r)>>1;
if(l>r1||r<l1||l1>r1) return ;
if(l>=l1&&r<=r1) return Add(t,d);
push(t);
modify(L(t),l,mid,l1,r1,d);
modify(R(t),mid+1,r,l1,r1,d);
update(t);
}
void solve(int n)
{
int i,mi=(h>>1);
for(i=1;i<=n;i++) a[i]=b[i];
sort(a+1,a+n+1,cmp);
if(a[n].x<w)
a[++n]=dot(w,0);
top1=top2=0;
for(i=1;i<=n;i++) z[i]=a[i].x;
m=n,z[++m]=0,z[++m]=w;
sort(z+1,z+m+1);
for(i=1;i<=n;i++)
a[i].x=map(a[i].x);
build(1,1,m);
if(a[1].x>1)
modify(1,1,m,1,1,h);
a[0].x=1;
for(i=1;i<=n;i++){
if(a[i].y<=mi){
modify(1,1,m,a[i].x,a[i].x,h);
ans=max(ans,A[1]+z[a[i].x]);
modify(1,1,m,a[st1[top1]].x,a[i].x-1,-a[i].y);
while(top1&&a[st1[top1]].y<=a[i].y){
modify(1,1,m,a[st1[top1-1]].x,a[st1[top1]].x-1,a[st1[top1]].y-a[i].y);
top1--;
}
st1[++top1]=i;
}
else{
modify(1,1,m,a[i].x,a[i].x,h);
ans=max(ans,A[1]+z[a[i].x]);
modify(1,1,m,a[st2[top2]].x,a[i].x-1,a[i].y-h);
while(top2&&a[st2[top2]].y>=a[i].y){
modify(1,1,m,a[st2[top2-1]].x,a[st2[top2]].x-1,a[i].y-a[st2[top2]].y);
top2--;
}
st2[++top2]=i;
}
}
}
int main()
{
int i;
scanf("%d %d %d",&w,&h,&n);
for(i=1;i<=n;i++)
scanf("%d %d",&b[i].x,&b[i].y);
solve(n);
for(i=1;i<=n;i++) swap(b[i].x,b[i].y);
swap(w,h);
solve(n);
cout<<ans*2;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
Wuvin |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2277 Byte |
Status |
AC |
Exec Time |
635 ms |
Memory |
16896 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:91:28: 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:93:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&b[i].x,&b[i].y);
^
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 |
628 ms |
16896 KB |
dia_02.txt |
AC |
627 ms |
16896 KB |
dia_03.txt |
AC |
629 ms |
16896 KB |
dia_04.txt |
AC |
632 ms |
16896 KB |
dial_01.txt |
AC |
628 ms |
16896 KB |
dial_02.txt |
AC |
628 ms |
16896 KB |
dial_03.txt |
AC |
629 ms |
16896 KB |
dial_04.txt |
AC |
633 ms |
16896 KB |
dial_05.txt |
AC |
635 ms |
16896 KB |
dial_06.txt |
AC |
633 ms |
16896 KB |
dialr_01.txt |
AC |
590 ms |
16640 KB |
dialr_02.txt |
AC |
596 ms |
16640 KB |
dialr_03.txt |
AC |
594 ms |
16640 KB |
dialr_04.txt |
AC |
592 ms |
16640 KB |
diar_01.txt |
AC |
627 ms |
16896 KB |
diar_02.txt |
AC |
634 ms |
16896 KB |
diar_03.txt |
AC |
633 ms |
16896 KB |
hand_01.txt |
AC |
6 ms |
12544 KB |
hand_02.txt |
AC |
6 ms |
12672 KB |
hand_03.txt |
AC |
6 ms |
12544 KB |
hand_04.txt |
AC |
6 ms |
12544 KB |
hand_05.txt |
AC |
6 ms |
12544 KB |
poc_t_1.txt |
AC |
6 ms |
12544 KB |
poc_t_2.txt |
AC |
6 ms |
12544 KB |
poc_t_3.txt |
AC |
6 ms |
12544 KB |
poc_t_4.txt |
AC |
6 ms |
12544 KB |
poc_t_5.txt |
AC |
6 ms |
12544 KB |
poc_w_1.txt |
AC |
6 ms |
12544 KB |
poc_w_2.txt |
AC |
6 ms |
12544 KB |
random0_01.txt |
AC |
592 ms |
16640 KB |
random0_02.txt |
AC |
593 ms |
16640 KB |
random0_03.txt |
AC |
615 ms |
16640 KB |
random1_01.txt |
AC |
593 ms |
16640 KB |
random1_02.txt |
AC |
593 ms |
16640 KB |
random1_03.txt |
AC |
597 ms |
16640 KB |
random1_04.txt |
AC |
595 ms |
16640 KB |
random1_05.txt |
AC |
597 ms |
16640 KB |
random1_06.txt |
AC |
593 ms |
16640 KB |
random1_07.txt |
AC |
592 ms |
16640 KB |
rect_01.txt |
AC |
592 ms |
16640 KB |
rect_02.txt |
AC |
591 ms |
16640 KB |
rect_03.txt |
AC |
591 ms |
16640 KB |
rect_04.txt |
AC |
593 ms |
16640 KB |
rect_05.txt |
AC |
588 ms |
16640 KB |
rect_06.txt |
AC |
585 ms |
16640 KB |
rect_07.txt |
AC |
593 ms |
16640 KB |
rect_08.txt |
AC |
591 ms |
16640 KB |
rect_09.txt |
AC |
592 ms |
16640 KB |
rect_10.txt |
AC |
593 ms |
16640 KB |
sample_01.txt |
AC |
6 ms |
12544 KB |
sample_02.txt |
AC |
6 ms |
12544 KB |
sample_03.txt |
AC |
6 ms |
12544 KB |
sample_04.txt |
AC |
6 ms |
12544 KB |
x_01.txt |
AC |
497 ms |
16896 KB |
x_02.txt |
AC |
498 ms |
16896 KB |
x_03.txt |
AC |
499 ms |
16896 KB |
x_04.txt |
AC |
502 ms |
16896 KB |