Codeforces 219E Parking Lot

夏季セミ中のDiv 2のE.

解法は簡単(距離をsetに突っ込んでおく)だけどiterationがめちゃくちゃ難しい。デバッグ大変だった。

よく一発ACしたなという感じ。

以下ソース

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int>pii;
int dist[200000];
int park[1000001];
int main()
{
	int num,query;
	scanf("%d%d",&num,&query);
	set<pii>se;
	set<pii>par;
	fill(park,park+1000001,-1);
	for(int p=0;p<query;p++)
	{/*
		set<pii>::iterator it=par.begin();
		printf("debug ");
		for(;;)
		{
			if(it==par.end())
			{
				break;
			}
			pii zan=*it;
			it++;
			printf("%d %d   ",zan.first,zan.second);
		}
		printf("\n");
		it=se.begin();
		printf("debug ");
		for(;;)
		{
			if(it==se.end())
			{
				break;
			}
			pii zan=*it;
			it++;
			printf("%d %d   ",zan.first,zan.second);
		}
		printf("\n");*/
		int za,zb;
		scanf("%d%d",&za,&zb);
		if(za==1)
		{
			set<pii>::iterator it;
			if(par.empty())
			{
				par.insert(make_pair(0,zb));
				printf("1\n");
				park[zb]=0;
				continue;
			}
			if(par.size()==1)
			{
				it=par.begin();
				pii zan=*it;
				if(zan.first>=num-zan.first-1)
				{
					par.insert(make_pair(0,zb));
					dist[0]=zan.first;
					se.insert(make_pair(zan.first,0));
					park[zb]=0;
					printf("1\n");
				}
				else
				{
					par.insert(make_pair(num-1,zb));
					dist[zan.first]=num-1-zan.first;
					se.insert(make_pair(num-1-zan.first,zan.first));
					park[zb]=num-1;
					printf("%d\n",num);
				}
				continue;
			}
			it=par.begin();
			pii zan=*it;
			int maxi=zan.first;
			int nn=0;
			int hab=zan.first;
			int flag=-1;
			it=se.end();
			it--;
			zan=*it;
			it=se.lower_bound(make_pair(zan.first,-1));
			pii zan2=*it;
			if(maxi<zan2.first/2)
			{
				maxi=zan2.first/2;
				nn=zan2.second;
				hab=zan2.first;
				flag=0;
			}
			if(zan.first%2==1)
			{
				it=se.lower_bound(make_pair(zan.first-1,-1));
				zan2=*it;
				if(maxi==zan2.first/2)
				{
					if(nn>zan2.second)
					{
						nn=zan2.second;
						hab=zan2.first;
						flag=0;
					}
				}
				if(maxi<zan2.first/2)
				{
					maxi=zan2.first/2;
					nn=zan2.second;
					hab=zan2.first;
					flag=0;
				}
			}
			it=par.end();
			it--;
			zan=*it;
			if(maxi<num-1-zan.first)
			{
				maxi=num-1-zan.first;
				nn=zan.first;
				hab=zan.first;
				flag=1;
			}
			it=se.lower_bound(make_pair(hab,nn));
			if(flag==-1)
			{
				se.insert(make_pair(maxi,0));
				par.insert(make_pair(0,zb));
				park[zb]=0;
				printf("1\n");

			}
			if(flag==1)
			{
				se.insert(make_pair(maxi,nn));
				par.insert(make_pair(nn+maxi,zb));
				park[zb]=num-1;
				printf("%d\n",num);
			}
			if(flag==0)
			{
				par.insert(make_pair(nn+maxi,zb));
				zan=*it;
				se.erase(it);
				se.insert(make_pair(maxi,zan.second));
				se.insert(make_pair(zan.first-maxi,nn+maxi));
				park[zb]=nn+maxi;
				printf("%d\n",nn+maxi+1);
			}
		}
		else
		{
			set<pii>::iterator it=par.lower_bound(make_pair(park[zb],-1));
			pii zan=*it;
			if(par.size()==1)
			{
				par.clear();
				se.clear();
				continue;
			}
			if(it==par.begin())
			{
				par.erase(it);
				it=par.begin();
				pii zan2=*it;
				it=se.lower_bound(make_pair(zan2.first-zan.first,zan.first));
				se.erase(it);
				continue;
			}
			it++;
			if(it==par.end())
			{
				it--;
				it--;
				pii zan2=*it;
				it++;
				par.erase(it);
				it=se.lower_bound(make_pair(zan.first-zan2.first,zan2.first));
				se.erase(it);
				continue;
			}
			it--;
			it--;
			pii zan2=*it;
			it++;
			it++;
			pii zan3=*it;
			it--;
			par.erase(it);
			it=se.lower_bound(make_pair(zan3.first-zan.first,zan.first));
			set<pii>::iterator it2=se.lower_bound(make_pair(zan.first-zan2.first,zan2.first));
			se.erase(it2);
			se.erase(it);
			se.insert(make_pair(zan3.first-zan2.first,zan2.first));
		}
	}
}