Baltic Olympiad in Informatics 2001

marsmap.cpp

// Ivan Carvalho
// Mars Map - Baltic Olympiad in Informatics 2001
// NKMARS - http://www.spoj.com/problems/NKMARS/
// O(n*log(n))
#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef pair<int,int> i2;typedef pair<int,i2> i3;typedef pair<int,i3> i4;
const int MAXN = 3*1e4 + 10;
vector<i4> sweep;
int ac[4*MAXN+40],soma[4*MAXN + 40],n,lastx,resp;
void add(int pos,int left,int right,int i,int j){
	if(left>right||left>j||right<i) return;
	if(left >= i && right <= j){
		ac[pos]++;
		soma[pos] = right - left + 1;
		return;
	}
	else{
		int mid = (left+right)/2;
		add(2*pos,left,mid,i,j);
		add(2*pos+1,mid+1,right,i,j);
		if(!ac[pos]) soma[pos] = soma[2*pos] + soma[2*pos+1];
	}
}
void remove(int pos,int left,int right,int i,int j){
	if(left>right||left>j||right<i) return;
	if(left >= i && right <= j){
		ac[pos]--;
		if(ac[pos] == 0){
			if(left == right) soma[pos] = 0;
			else soma[pos] = soma[2*pos] + soma[2*pos+1];
		}
	}
	else{
		int mid = (left+right)/2;
		remove(2*pos,left,mid,i,j);
		remove(2*pos+1,mid+1,right,i,j);
		if(!ac[pos]) soma[pos] = soma[2*pos] + soma[2*pos+1];
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1++;x2++;y1++;y2++;
		sweep.push_back(MP(x1,MP(1,MP(y1,y2-1))));
		sweep.push_back(MP(x2,MP(-1,MP(y1,y2-1))));
	}
	sort(sweep.begin(),sweep.end());
	for(int i=0;i<(int)sweep.size();i++){
		int delta = sweep[i].second.first;
		int l = sweep[i].second.second.first;
		int r = sweep[i].second.second.second;
		int x = sweep[i].first;
		resp += soma[1]*(x - lastx);
		lastx = x;
		if(delta == 1) add(1,1,MAXN,l,r);
		else remove(1,1,MAXN,l,r);
	}
	cout << resp << endl;
	return 0;
}