JOI 春合宿 2008 Day 3 Origami

JOI

問題文はちゃんと読みましょう


mapで数えるだけの問題を2次元座圧+2次元imosでやりました。
普通にやったらMLEするので、平面走査風にやってメモリ節約しました。

int imos[10050],cnt[10050];
int a,b,n;
int p[5050],q[5050],r[5050],s[5050];
vector<int> vx,vy;
vector<T> event;
ll size(int x,int y)
{
	if(x+1>=(int)vx.size()||y+1>=(int)vy.size())return 0ll;
	return (ll)(vx[x+1]-vx[x])*(ll)(vy[y+1]-vy[y]);
}
int main()
{
	scanf("%d",&n);
	scanf("%d %d",&a,&b);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]);
		p[i]--;q[i]--;
		vx.pb(p[i]);vy.pb(q[i]);vx.pb(r[i]);vy.pb(s[i]);
	}
	sort(all(vx));
	sort(all(vy));
	vx.erase(unique(all(vx)),vx.end());
	vy.erase(unique(all(vy)),vy.end());
	for(int i=0;i<n;i++)
	{
		p[i]=lower_bound(all(vx),p[i])-vx.begin();
		q[i]=lower_bound(all(vy),q[i])-vy.begin();
		r[i]=lower_bound(all(vx),r[i])-vx.begin();
		s[i]=lower_bound(all(vy),s[i])-vy.begin();
		//printf("%d %d %d %d\n",p[i],q[i],r[i],s[i]);
		event.pb(T(P(p[i],q[i]),1));
		event.pb(T(P(p[i],s[i]),-1));
		event.pb(T(P(r[i],q[i]),-1));
		event.pb(T(P(r[i],s[i]),1));
	}
	sort(all(event));
	int SX = vx.size(),SY = vy.size();
	int id = 0;
	int ans_sz = 0;
	ll ans_num = 0ll;
	for(int i=0;i<=SX;i++)
	{
		if(!(id<event.size()))break;
		if(event[id].fi.fi!=i)continue;
		memset(cnt,0,sizeof(cnt));
		while(id<event.size()&&event[id].fi.fi==i)
		{
			cnt[event[id].fi.sec]+=event[id].sec;
			id++;
		}
		for(int j=0;j<=SY;j++)cnt[j+1]+=cnt[j];
		for(int j=0;j<=SY;j++)
		{
			imos[j]+=cnt[j];
			if(ans_sz<imos[j])
			{
				ans_sz = imos[j];
				ans_num = size(i,j);
			}
			else if(ans_sz==imos[j])
			{
				ans_num += size(i,j);
			}
		}
	}
	printf("%d\n",ans_sz);
	printf("%lld\n",ans_num);
	return 0;
}