DSL_4_A: Union of Rectangles - sinapusu2002 @ ウィキ

DSL_4_A: Union of Rectangles
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A
左下から右上へ細かい四角に区切りながら面積を集計するだけです。

#include<stdio.h>
#include<iostream>
#include<map>
#include<set>
int main(){
int n;
long long int ans=0;
std::map<long long int,std::map<long long int,int> > memo;
std::set<long long int> ys;

scanf("%d",&n);
for(int i=0;i<n;i++){
	long long int x1,y1,x2,y2;
	std::cin>>x1>>y1>>x2>>y2;
	memo[y1][x1]++;
	memo[y1][x2]--;
	memo[y2][x1]--;
	memo[y2][x2]++;
	ys.insert(y1);
	ys.insert(y2);
}
std::set<long long int>::iterator it1,it2;
it1=ys.begin();
long long int y=(*it1);
std::map<long long int,int>::iterator mIt;
std::map<long long int,int> count;
for(mIt=memo[y].begin();mIt!=memo[y].end();mIt++){
	long long int x=(*mIt).first;
	int c=(*mIt).second;
	count[x]=c;
}
it1=ys.begin();
it2=ys.begin();
for(it2++;it2!=ys.end();it2++,it1++){
	long long int y2=(*it2);
	long long int y1=(*it1);
	mIt=count.begin();
	if(mIt!=count.end()){
		long long int x1=(*mIt).first;
		int c=(*mIt).second;
		mIt++;
		while(1){
			while(c>0){
				c+=(*mIt).second;
				//std::cout<<" <x1="<<x1<<" "<<(*mIt).first<<" "<<(*mIt).second<<" "<<c<<"> ";
				if(c==0)break;
				mIt++;
				if(mIt==count.end()){
					mIt--;
					break;
				}
			}
			
			long long int x2=(*mIt).first;
			ans+=((y2-y1)*(x2-x1));
			//printf("(d=x1=%lld y1=%lld x2=%lld y2=%lld)\n",x1,y1,x2,y2);
			//std::cout<<"x1="<<x1<<" "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<"\n";
			mIt++;
			if(mIt==count.end())break;
			c=(*mIt).second;
			x1=(*mIt).first;
			mIt++;
		}
	}
	//printf("(y2=%lld ans=%lld)\n",y2,ans);
	//std::cout<<"\n("<<y2<<" "<<ans<<")\n";
	for(mIt=memo[y2].begin();mIt!=memo[y2].end();mIt++){
		long long int x1=(*mIt).first;
		int c=(*mIt).second;
		count[x1]+=c;
	}
	std::set<long long int> dell;
	for(mIt=count.begin();mIt!=count.end();mIt++){
		if((*mIt).second==0){
			dell.insert((*mIt).first);
		}
	}
	std::set<long long int>::iterator it3;
	for(it3=dell.begin();it3!=dell.end();it3++){
		count.erase((*it3));
	}
}
printf("%lld\n",ans);
}