NEERC- Subregional 2014 - Problem J

gistfile1.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define dprint(v) cout << #v"=" << v << endl
#define forr(i, a, b) for(int i=(a); i<(b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforn(i, n) for(int i=(n)-1; i>=0; i--)
#define forall(it,v) for(typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
typedef long long ll;
#define ii pair <pair<ll , ll>, pair <ll, pair <ll,ll> > >
#define mkp make_pair
#define fst first
#define snd second
#define pb push_back

#define INF 10000000
#define tipo ii // ((A,B), (C,(D,E)) donde
// A = cansancio al dia B-1 ... C simboliza el contest participado para llegar ahi, D la anterior posicion de la que llegamos y E la actual posicion. (C,D,E) se usa para reconstruir solamente



ii operacion (ii a, ii b) // Es un min, que devuelve cual de los dos esta menos cansado
{
	//~ dprint(a.snd);
	//~ dprint (b.snd);
	if (a.fst.snd > b.fst.snd){
		if (a.fst.snd == INF) return b;
		if ((b.fst.fst >> (a.fst.snd - b.fst.snd)) < a.fst.fst)
			return b;
		else
			return a;
	}
	if (b.fst.snd == INF) return a;
	if ((a.fst.fst >> (b.fst.snd - a.fst.snd)) < b.fst.fst)
		return a;
	return b;	
}


//Dado un arreglo y una operacion asociativa con neutro, get(i, j) opera sobre el rango [i, j).
#define MAXN 1000001
const ii neutro=mkp (mkp(0,INF), mkp (-1,mkp(-1,-1))); 
struct RMQ{
	int sz;
	tipo t[4*MAXN];
	tipo &operator[](int p){return t[sz+p];}
	void init(int n){//O(nlgn)
		sz = 1 << (32-__builtin_clz(n));
		forr(i, sz, 2*sz) t[i]=neutro;
	}
	void updall(){//O(n)
		dforn(i, sz) t[i]=operacion(t[2*i], t[2*i+1]);}
	tipo get(int i, int j){return get(i,j,1,0,sz);}
	tipo get(int i, int j, int n, int a, int b){//O(lgn)
		if(j<=a || i>=b) return neutro;
		if(i<=a && b<=j) return t[n];
		int c=(a+b)/2;
		return operacion(get(i, j, 2*n, a, c), get(i, j, 2*n+1, c, b));
	}
	void set(int p, tipo val){//O(lgn)
		for(p+=sz; p>0 && t[p]!=val;){
			t[p]=val;
			p/=2;
			val=operacion(t[p*2], t[p*2+1]);
		}
	}
}a;
//Usage:
//~ cin >> n; rmq.init(n); forn(i, n) cin >> rmq[i]; rmq.updall();

ll d[200100],l[200100],h[200100]; //d: dia, l: minimo, h:maximo
ii act[200100]; //usado para guardar actualizaciones antes de realizarlas

ll n,s,dt,k;
ii aux;

void f(int i, int cant)
{
	if (a[i].snd.snd.fst == -1){
		cout << cant << endl;
		return;
	}

	f (a[i].snd.snd.fst, cant+1);
	
	if (cant)
		cout << a[i].snd.fst+1 << " ";
	else
		cout << a[i].snd.fst+1 << endl;
}


int main()
{
#ifndef ONLINE_JUDGE
	//~ freopen("e.in", "r", stdin);
#endif
	while (cin >> n >> s >> dt){
		forn (i,n)
			cin >> d[i] >> l[i] >> h[i];
			
		a.init (1000001);
		a[s]=mkp (mkp (0,-1),mkp (-1,mkp(-1,s)));
		a.updall();


		forn (i,n){
			
			
			for (int j = i;j < n && d[i] == d[j];j++){ //Todos los contest del mismo dia
				act[j] = a.get (l[j], h[j]);
		
		
				if (act[j].fst.snd != INF){

					act[j].fst.fst >>= (d[j]-act[j].fst.snd);

					act[j].fst.snd = d[j]+1;
					act[j].fst.fst += dt;
					
					act[j].snd.fst = j; //contest!
					act[j].snd.snd.fst = act[j].snd.snd.snd; // poder anterior
					
		
				}
				//~ dprint (j);
				//~ dprint(act[j].fst.fst);
				//~ dprint(act[j].fst.snd);
			}
			
			for (k = i;k < n && d[i] == d[k];k++) // Los actualizo a todos juntos
				if (act[k].fst.snd != INF){
					int exp = h[k]-act[k].fst.fst+dt;
					act[k].snd.snd.snd = exp; // poder actual
					//~ dprint(exp);
					a.set (exp, operacion (act[k], a[exp]));
			
			
			}
			i = k-1; 
				
		}	
		

		
		dforn (i, 1000001) // Busco el maximo "poder"
			if (a[i].fst.snd < INF){
				cout << i << " ";
				f(i,0);
				break;
			}
			
			
	}

	
	
	
    return 0;
}