Seletiva IOI 2013

etiqueta.cpp

// Ivan Carvalho
// Etiqueta - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
#define MAXN 200101
#define MP make_pair
ll arvore[4*MAXN],lazy[4*MAXN];
ll query(ll pos, ll left, ll right, ll i, ll j){
	if (lazy[pos]!= 0){
		arvore[pos] = (right - left + 1) * lazy[pos];
		if (left != right){
			lazy[2*pos+1] = lazy[pos];
			lazy[2*pos+2] = lazy[pos];
		}
		lazy[pos] = 0;
	}
	if (left > right || left > j || right < i) return 0;
	if (left >= i && right <= j){
		return arvore[pos];
	}
	ll mid = (left+right)/2;
	ll p1 = query(2*pos+1,left,mid,i,j);
	ll p2 = query(2*pos+2,mid+1,right,i,j);
	return p1 + p2;
}
void update(ll pos, ll left, ll right, ll i, ll j, ll val){
	if (lazy[pos]!= 0){
		arvore[pos] = (right - left + 1) * lazy[pos];
		if (left != right){
			lazy[2*pos+1] = lazy[pos];
			lazy[2*pos+2] = lazy[pos];
		}
		lazy[pos] = 0;
	}
	if (left > right || left > j || right < i) return;
	if (left >= i && right <= j){
		arvore[pos] = (right - left + 1) * val;
		if (left != right){
			lazy[2*pos+1] = val;
			lazy[2*pos+2] = val;
		}
		return ; 
	}
	ll mid = (left+right)/2;
	update(2*pos+1,left,mid,i,j,val);
	update(2*pos+2,mid+1,right,i,j,val);
	arvore[pos] = arvore[2*pos+1] + arvore[2*pos+2];
}
int main(){
	ll a,n;
	scanf("%lld %lld",&a,&n);
	vector<iii> vetor;
	for(ll i=1;i<=n;i++){
		ll x_i,x_f,y;
		scanf("%lld %lld %lld",&x_i,&x_f,&y);
		vetor.push_back(MP(y,MP(x_i,x_f)));
	}
	sort(vetor.begin(),vetor.end());
	for(ll i=0;i<n;i++){
		ll  y = vetor[i].first, x_i = vetor[i].second.first, x_f = vetor[i].second.second;
		update(0,0,2*a,x_i,x_f-1,y);
	}
	printf("%lld\n",query(0,0,2*a,0,2*a));
	return 0;
}