POJ.3171 Cleaning Shifts

1.Problem
http://poj.org/problem?id=3171

2.Idea
dp + seg tree

3.Source

 const int MAX_N = 10004;  
 const int MAX_M = 86399;  
 const ll INF = 1e18;  
 template<class T>  
 struct SegTree {  
      int NN;  
      vector<T> seg;  
      T def; // default vale  
      T func(T a, T b) {  
           return min(a, b);  
      }  
      void gather(int u) {  
           seg[u] = func(seg[u * 2 + 1], seg[u * 2 + 2]);  
      }  
      void init(int N, T d) {  
           def = d;  
           NN = 1;  
           while (NN < N)  
                NN *= 2;  
           seg = vector<T>(2 * NN - 1, def);  
           // for (int i = 0; i < N; i++) {  
           //   seg[NN - 1 + i] = inp[i];  
           // }  
           build(0);  
      }  
      void build(int u) {  
           if (u >= NN - 1) { // leaf  
                return;  
           }  
           build(u * 2 + 1);  
           build(u * 2 + 2);  
           gather(u);  
      }  
      void _update(int idx, T val, int u, int l, int r) {  
           if (l > idx || r <= idx) {  
                return;  
           }  
           if (l == idx && idx + 1 == r) {  
                seg[u] = val;  
                return;  
           }  
           int m = (l + r) / 2;  
           _update(idx, val, u * 2 + 1, l, m);  
           _update(idx, val, u * 2 + 2, m, r);  
           gather(u);  
      }  
      T _query(int a, int b, int u, int l, int r) {  
           if (l >= b || r <= a) {  
                return def;  
           }  
           if (a <= l && r <= b) {  
                return seg[u];  
           }  
           int m = (l + r) / 2;  
           T res1 = _query(a, b, u * 2 + 1, l, m);  
           T res2 = _query(a, b, u * 2 + 2, m, r);  
           return func(res1, res2);  
      }  
      void update(int idx, T val) {  
           _update(idx, val, 0, 0, NN);  
      }  
      T query(int a, int b) {  
           return _query(a, b, 0, 0, NN);  
      }  
 };  
 int N, M, E;  
 ll dp[MAX_M + 1];  
 SegTree<ll> seg;  
 struct Cow {  
      ll s, t, c;  
      bool operator < (const Cow &a)const {  
           if (s == a.s) return t < a.t;  
           else return s < a.s;  
      }  
 } Cows[MAX_N];  
 int main()  
 {  
      scanf("%d%d%d", &N, &M, &E);  
      E -= M;  
      for (int i = 0; i < N; i++) {  
           scanf("%lld%lld%lld", &Cows[i].s, &Cows[i].t, &Cows[i].c);  
           Cows[i].s -= M;  
           Cows[i].t -= M;  
      }  
      sort(Cows, Cows + N);  
      fill(dp, dp + E + 1, INF);  
      seg.init(E + 1, INF);  
      int i1 = 0;  
      while (i1 < N && Cows[i1].s == 0) {  
           dp[Cows[i1].t] = min(dp[Cows[i1].t], Cows[i1].c);  
           seg.update(Cows[i1].t, Cows[i1].c);  
           i1++;  
      }  
      for (int i = i1; i < N; i++) {  
           ll v = min(dp[Cows[i].t], seg.query(Cows[i].s - 1, Cows[i].t + 1) + Cows[i].c);  
           dp[Cows[i].t] = v;  
           seg.update(Cows[i].t, v);  
      }  
      if (dp[E] == INF) cout << -1 << endl;  
      else cout << dp[E] << endl;  
      return 0;  
 }