APIO 2012 Guard

http://d1yjytat4ps3ku.cloudfront.net/final-AeF9DxEp/apio2012-jpn.pdf
たぶんここら辺に日本語の問題文があります

解法

10%：全探索にしてはオーダー大きいし謎
50%：整数計画＋多少の枝刈で通った。オーダーよく分からない
100%：変な貪欲+DP　別解多分ある

まず、ここには絶対忍者いない！！というところをマーク。
忍者いる可能性ありの区間も、完全に内側に別の区間があるものは無視する。
こうすると、すべての区間[ai,bi]をai

#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;
static const int INF =500000000;
typedef pair<int,int> pi;
int n,m,k;
int ng[100005],ngsum[100005];
pi range[100005];
int dp[100005],dp2[100005];
bool cmp(const pi& a,const pi& b){
	if(a.first!=b.first) return a.first<b.first;
	return a.second>b.second;
}
bool judge(const pi& a){
	return a.first==-1;
}
set<int> posi;
int getclose(int a){
	set<int>::iterator it=posi.lower_bound(a);
	--it;
	return *it;
}
int oksum[100005];
int main(){
	scanf("%d%d%d",&n,&k,&m);
	int cnt=0;
	for(int i=0;i<m;++i){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;
		if(c==0){
			++ng[a];
			--ng[b];
		}else range[cnt++]=make_pair(a,b);
	}
	sort(range,range+cnt,cmp);
	int border=INF;
	for(int i=cnt-1;i>=0;--i){
		if(range[i].second>=border){
			range[i]=make_pair(-1,-1);
		}else{
			border=range[i].second;
		}
	}
	cnt=remove_if(range,range+cnt,judge)-range;

	ngsum[0]=ng[0];
	for(int i=0;i<n-1;++i) ngsum[i+1]=ngsum[i]+ng[i+1];
	oksum[0]=0;
	for(int i=0;i<n;++i) oksum[i+1]=oksum[i]+(ngsum[i]==0);
	for(int i=0;i<n;++i) if(!ngsum[i]) posi.insert(i);
	if(posi.size()==k){
		int nev=1;
		for(int i=0;i<n;++i) if(!ngsum[i]) printf("%d\n",i+1),nev=0;
		if(nev) puts("-1");
		return 0;
	}
	posi.insert(-1);
	for(int i=cnt-1;i>=0;--i){
		int nxt=lower_bound(range,range+cnt,make_pair(getclose(range[i].second),INF))-range;
		dp[i]=dp[nxt]+1;
	}
	vector<int> cand,ever,bel;
	int num=0;
	for(int i=0;i<cnt;){
		cand.push_back(getclose(range[i].second));
		ever.push_back(num);
		bel.push_back(i);
		++num;
		int nxt=lower_bound(range,range+cnt,make_pair(getclose(range[i].second),INF))-range;
		i=nxt;
	}
	int nev=1;
	for(int hog=0;hog<cand.size();++hog){
		int i=cand[hog];
		int belong=bel[hog];
		if(oksum[i]-oksum[range[belong].first]<=0){
			printf("%d\n",i+1);
			nev=0;
			continue;
		}
		int back=getclose(i);
		int begin=lower_bound(range,range+cnt,make_pair(back,INF))-range;
		if(dp[begin]+ever[hog]+1>k){
			printf("%d\n",i+1);
			nev=0;
		}
	}
	if(nev) puts("-1");

	return 0;
}