POJ3171 Cleaning Shifts

普通にDPと思いきやうまくDPできない(N^2になる)
とりあえずsegtree使ってDPしてN log Nにおとす。通る。
はじめてのsegtreeなのっ！

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define mt(A,B,C) make_pair(make_pair(A,B),C)
typedef long long ll;
typedef pair<pair<int,int>,int> pi3;
ll seg[262144];
void init()
{
	for(int i=0;i<262144;i++)
	{
		seg[i]=1000000000000000L;
	}
}
void update(int a,ll b)
{
	a+=131072;
	seg[a]=min(b,seg[a]);
	for(;;)
	{
		a/=2;
		if(a==0)
		{
			break;
		}
		seg[a]=min(seg[a*2],seg[a*2+1]);
	}
}
ll query(int beg,int end,int node,int nb,int ne)
{
	if(beg>ne||end<nb)
	{
		return 1000000000000000L;
	}
	if(beg<=nb&&end>=ne)
	{
		return seg[node];
	}
	return min(query(beg,end,node*2,nb,(nb+ne)/2),query(beg,end,node*2+1,(nb+ne)/2+1,ne));
}
ll kei(int a,int b,int c,int d,int e)
{
	return query(a+131072,b+131072,c,d+131072,e+131072);
}
int main()
{
	init();
	int cow,beg,end;
	scanf("%d%d%d",&cow,&beg,&end);
	vector<pi3>vec;
	for(int i=0;i<cow;i++)
	{
		int za,zb,zc;
		scanf("%d%d%d",&za,&zb,&zc);
		vec.push_back(mt(zb+1,za,zc));
	}
	sort(vec.begin(),vec.end());
	update(beg,0);
	for(int j=0;j<cow;j++)
	{
		swap(vec[j].first.second,vec[j].first.first);
		update(vec[j].first.second,kei(vec[j].first.first,vec[j].first.second,1,0,131071)+vec[j].second);
		}
	if(seg[end+131073]==1000000000000000L)
	{
		printf("-1\n");
	}
	else
	{
		printf("%lld\n",seg[end+131073]);
	}
}