Submission #1386008


Source Code Expand

#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;
 
const int N=1050005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}
int w,h,n,cnt,ans,x[N],y[N],yy[N],sta[N][2],g[N][2],top[2];
int p[N<<1],flag[N<<1];
 
inline void ins(int x){if(x>=1&&x<h) yy[++cnt]=x;}
inline int get(int y){return lower_bound(yy+1,yy+cnt+1,y)-yy;}
inline void add(int k,int b){p[k]+=b;flag[k]+=b;}
inline void push(int k){
	if(!flag[k]) return;
	add(ls,flag[k]);add(rs,flag[k]);
	flag[k]=0;
}
void ch(int l,int r,int x,int y,int k,int b){
	if(x<=l&&r<=y){add(k,b);return;}
	push(k);
	int mid=l+r>>1;
	if(x<=mid) ch(l,mid,x,y,ls,b);
	if(y>mid) ch(mid+1,r,x,y,rs,b);
	p[k]=max(p[ls],p[rs]);
}
void build(int l,int r,int k){
	if(l==r){p[k]=-yy[l];return;}
	int mid=l+r>>1;
	build(l,mid,ls);build(mid+1,r,rs);
	p[k]=max(p[ls],p[rs]);
}
void solve(int mid){
	clr(flag,0);clr(top,0);cnt=0;
	ins(1);ins(h-1);
	for(int i=1;i<=n;i++){
		ins(y[i]);
		ins(y[i]-1);
		ins(y[i]+1);
	}
	sort(yy+1,yy+cnt+1);
	cnt=unique(yy+1,yy+cnt+1)-yy-1;
	if(!cnt){printf("%d\n",(w+h)*2);exit(0);}
	build(1,cnt,1);
	for(int i=1;i<=cnt;i++)
		g[i][0]=mid,g[i][1]=w-mid;
	for(int i=1;i<=n;i++){
		if(!y[i]||y[i]==h) continue;
		if(x[i]<=mid) gmin(g[get(y[i])][0],mid-x[i]); else gmin(g[get(y[i])][1],x[i]-mid);
	}
	for(int i=1;i<=cnt;i++){
		for(int x=0;x<2;x++){
			int last=i;
			ch(1,cnt,i,i,1,g[i][x]);
			while(top[x]&&g[sta[top[x]][x]][x]>g[i][x]){
				int l=sta[top[x]-1][x]+1,r=sta[top[x]][x];
				ch(1,cnt,l,r,1,g[i][x]-g[r][x]);
				top[x]--;
			}
			sta[++top[x]][x]=i;
		}
		gmax(ans,(p[1]+yy[i]+2)*2);
	}
}
 
int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d%d",&w,&h,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	solve(w/2);
	for(int i=1;i<=n;i++)
		swap(x[i],y[i]);
	swap(w,h);solve(w/2);
	printf("%d\n",max(ans,max(w,h)*2+2));
	return 0;
}

Submission Info

Submission Time
Task I - 90 and 270
User vjudge1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2813 Byte
Status WA
Exec Time 7 ms
Memory 20864 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:102: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:104:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x[i],&y[i]);
                            ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1500
Status
WA × 2
WA × 46
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt WA 6 ms 20736 KB
001.txt WA 6 ms 20736 KB
002.txt WA 6 ms 20736 KB
003.txt WA 6 ms 20736 KB
004.txt WA 6 ms 20736 KB
005.txt WA 6 ms 20736 KB
006.txt WA 6 ms 20736 KB
007.txt WA 6 ms 20736 KB
008.txt WA 6 ms 20736 KB
009.txt WA 7 ms 20736 KB
010.txt WA 6 ms 20736 KB
011.txt WA 6 ms 20736 KB
012.txt WA 6 ms 20736 KB
013.txt WA 6 ms 20736 KB
014.txt WA 6 ms 20736 KB
015.txt WA 6 ms 20736 KB
016.txt WA 6 ms 20736 KB
017.txt WA 6 ms 20736 KB
018.txt WA 6 ms 20736 KB
019.txt WA 6 ms 20736 KB
020.txt WA 6 ms 20736 KB
021.txt WA 6 ms 20736 KB
022.txt WA 6 ms 20736 KB
023.txt WA 6 ms 20736 KB
024.txt WA 6 ms 20736 KB
025.txt WA 6 ms 20736 KB
026.txt WA 6 ms 20736 KB
027.txt WA 6 ms 20736 KB
028.txt WA 6 ms 20736 KB
029.txt WA 6 ms 20736 KB
030.txt WA 6 ms 20736 KB
031.txt WA 6 ms 20736 KB
032.txt WA 6 ms 20736 KB
033.txt WA 6 ms 20736 KB
034.txt WA 6 ms 20736 KB
035.txt WA 6 ms 20736 KB
036.txt WA 6 ms 20736 KB
037.txt WA 6 ms 20736 KB
038.txt WA 6 ms 20736 KB
039.txt WA 6 ms 20864 KB
040.txt WA 6 ms 20736 KB
041.txt WA 6 ms 20736 KB
042.txt WA 6 ms 20736 KB
043.txt WA 6 ms 20736 KB
example0.txt WA 6 ms 20736 KB
example1.txt WA 6 ms 20736 KB