Submission #1832943


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=300010;
int xm,ym,n,ans=0;
struct Pt{
	int x,y;
	inline friend bool operator < (const Pt &a,const Pt &b){
		return a.y!=b.y?a.y<b.y:a.x<b.x;
	}
	inline friend ostream & operator << (ostream & out,const Pt &b){
		out<<"("<<b.x<<","<<b.y<<")";
		return out;
	}
}pt[N],lstl[N],lstr[N];
int lsl,lsr;
struct intv{
	int l,r,x;
	inline friend bool operator < (const intv &a,const intv &b){
		return a.l<b.l;
	}
}*lv=new intv[N<<1],*rv=new intv[N<<1];
int lvl,lvr;
struct intvcmp2{
	inline bool operator () (const intv &a,const intv &b){
		return a.r!=b.r?a.r<b.r:a.x<b.x;
	}
};
inline void work2(){
	typedef set<intv,intvcmp2>::iterator iter;
	set<intv,intvcmp2>s;
	for(int i=1,j=1;i<=lvl;i++){
		for(;j<=lvr&&rv[j].l<=lv[i].l;j++){
			if(rv[j].r>lv[i].l){
				iter it=s.insert(rv[j]).first;
				if(it!=s.begin()){
					iter bef=it;
					bef--;
					if(bef->r+bef->x>=it->r+it->x){
						s.erase(it);
						continue;
					}
					if(bef->r==it->r){
						s.erase(bef);
					}
				}
				for(iter it2;it2=it,it2++,it2!=s.end()&&it2->r+it2->x<=it->r+it->x;s.erase(it2));
			}
		}
		for(;assert(!s.empty()),s.begin()->r<=lv[i].l;s.erase(s.begin()));
		iter it=s.lower_bound((intv){0,lv[i].r+1,-1});
		if(it!=s.end()){
			assert(it->r>lv[i].r);
			apmax(ans,it->x-lv[i].x+lv[i].r-lv[i].l);
		}
		if(it!=s.begin()){
			it--;
			assert(it->r<=lv[i].r);
			apmax(ans,it->x-lv[i].x+it->r-lv[i].l);
		}
	}
}
int stk[N],ss;
int pre[N],nxt[N];
inline void work(){
	sort(pt+1,pt+n+1);
	lsl=lsr=lvl=lvr=0;
	int m=xm>>1;
	for(int i=1;i<=n;i++){
		(pt[i].x<=m?lstl[++lsl]:lstr[++lsr])=pt[i];
	}
	{//left hand side
		lstl[0].y=0;
		stk[ss=0]=0;
		for(int i=1;i<=lsl;i++){
			if(i<lsl&&lstl[i+1].y==lstl[i].y)continue;
			for(;ss&&lstl[stk[ss]].x<=lstl[i].x;ss--);
			pre[i]=lstl[stk[ss]].y;
			stk[++ss]=i;
		}
		lstl[0].y=ym;
		stk[ss=0]=0;
		for(int i=lsl;i>=1;i--){
			if(i<lsl&&lstl[i+1].y==lstl[i].y)continue;
			for(;ss&&lstl[stk[ss]].x<=lstl[i].x;ss--);
			nxt[i]=lstl[stk[ss]].y;
			stk[++ss]=i;
		}
		int last=0;
		for(int i=1;i<=lsl;i++){
			if(i<lsl&&lstl[i+1].y==lstl[i].y)continue;
			lv[++lvl]=(intv){pre[i],nxt[i],lstl[i].x};
			lv[++lvl]=(intv){last,lstl[i].y,0};
			last=lstl[i].y;
		}
		assert(last!=ym);
		lv[++lvl]=(intv){last,ym,0};
		sort(lv+1,lv+lvl+1);
	}
	{//right hand side
		lstr[0].y=0;
		stk[ss=0]=0;
		for(int i=1;i<=lsr;i++){
			if(i>1&&lstr[i-1].y==lstr[i].y)continue;
			for(;ss&&lstr[stk[ss]].x>=lstr[i].x;ss--);
			pre[i]=lstr[stk[ss]].y;
			stk[++ss]=i;
		}
		lstr[0].y=ym;
		stk[ss=0]=0;
		for(int i=lsr;i>=1;i--){
			if(i>1&&lstr[i-1].y==lstr[i].y)continue;
			for(;ss&&lstr[stk[ss]].x>=lstr[i].x;ss--);
			nxt[i]=lstr[stk[ss]].y;
			stk[++ss]=i;
		}
		int last=0;
		for(int i=1;i<=lsr;i++){
			if(i>1&&lstr[i-1].y==lstr[i].y)continue;
			rv[++lvr]=(intv){pre[i],nxt[i],lstr[i].x};
			rv[++lvr]=(intv){last,lstr[i].y,xm};
			last=lstr[i].y;
		}
		assert(last!=ym);
		rv[++lvr]=(intv){last,ym,xm};
		sort(rv+1,rv+lvr+1);
	}
	work2();
	swap(lv,rv),swap(lvl,lvr);
	for(int i=1;i<=lvl;i++){
		lv[i].x=xm-lv[i].x;
	}
	for(int i=1;i<=lvr;i++){
		rv[i].x=xm-rv[i].x;
	}
	work2();
}
int main(){
	xm=ni,ym=ni,n=ni;
	for(int i=1;i<=n;i++){
		pt[i]=(Pt){ni,ni};
		if(pt[i].x==0||pt[i].x==xm||pt[i].y==0||pt[i].y==ym){
			--i,--n;
		}
	}
	work();
	swap(xm,ym);
	for(int i=1;i<=n;i++){
		swap(pt[i].x,pt[i].y);
	}
	work();
	printf("%d\n",ans<<1);
	return 0;
}

Submission Info

Submission Time
Task F - Snuke's Coloring 2
User sshockwave
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 4114 Byte
Status AC
Exec Time 293 ms
Memory 24704 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 57
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 220 ms 18688 KB
dia_02.txt AC 214 ms 18176 KB
dia_03.txt AC 218 ms 18560 KB
dia_04.txt AC 224 ms 18816 KB
dial_01.txt AC 225 ms 19072 KB
dial_02.txt AC 291 ms 23552 KB
dial_03.txt AC 285 ms 22656 KB
dial_04.txt AC 293 ms 24704 KB
dial_05.txt AC 231 ms 19968 KB
dial_06.txt AC 229 ms 18304 KB
dialr_01.txt AC 210 ms 18176 KB
dialr_02.txt AC 220 ms 19840 KB
dialr_03.txt AC 216 ms 20992 KB
dialr_04.txt AC 211 ms 19456 KB
diar_01.txt AC 241 ms 18304 KB
diar_02.txt AC 254 ms 22144 KB
diar_03.txt AC 257 ms 23168 KB
hand_01.txt AC 3 ms 6400 KB
hand_02.txt AC 3 ms 6400 KB
hand_03.txt AC 3 ms 6400 KB
hand_04.txt AC 3 ms 6400 KB
hand_05.txt AC 3 ms 6400 KB
poc_t_1.txt AC 3 ms 6400 KB
poc_t_2.txt AC 3 ms 6400 KB
poc_t_3.txt AC 3 ms 6400 KB
poc_t_4.txt AC 3 ms 6400 KB
poc_t_5.txt AC 3 ms 6400 KB
poc_w_1.txt AC 3 ms 6400 KB
poc_w_2.txt AC 3 ms 6400 KB
random0_01.txt AC 212 ms 18688 KB
random0_02.txt AC 212 ms 18944 KB
random0_03.txt AC 222 ms 19840 KB
random1_01.txt AC 211 ms 20608 KB
random1_02.txt AC 211 ms 18688 KB
random1_03.txt AC 216 ms 22272 KB
random1_04.txt AC 213 ms 21760 KB
random1_05.txt AC 214 ms 21504 KB
random1_06.txt AC 206 ms 20352 KB
random1_07.txt AC 203 ms 19968 KB
rect_01.txt AC 208 ms 21376 KB
rect_02.txt AC 210 ms 19840 KB
rect_03.txt AC 212 ms 20608 KB
rect_04.txt AC 202 ms 22272 KB
rect_05.txt AC 199 ms 20864 KB
rect_06.txt AC 186 ms 19840 KB
rect_07.txt AC 212 ms 19968 KB
rect_08.txt AC 209 ms 18944 KB
rect_09.txt AC 213 ms 19968 KB
rect_10.txt AC 211 ms 19968 KB
sample_01.txt AC 3 ms 6400 KB
sample_02.txt AC 3 ms 6400 KB
sample_03.txt AC 3 ms 6400 KB
sample_04.txt AC 3 ms 6400 KB
x_01.txt AC 212 ms 18048 KB
x_02.txt AC 211 ms 19712 KB
x_03.txt AC 209 ms 18176 KB
x_04.txt AC 219 ms 18688 KB