railway.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream.h>
#include <iostream.h>

ifstream fin("railway.in");
ofstream fout("railway.out");
//#define fout cout

struct tree {
   int l, r, max, occur; 
   tree *left, *right;
};

tree* newtree(int l, int r, int max = 0, int occur = 0) {
   tree* t = new tree;
   t->l = l, t->r = r, t->max = max, t->occur = occur;
   t->left = t->right = NULL;
   return t;
}

void buildtree(int l, int r, tree* t) {
   if (l == r) return;
   int m = (l + r) / 2;
   t->left = newtree(l, m);
   t->right = newtree(m + 1, r);
   buildtree(l, m, t->left);
   buildtree(m + 1, r, t->right);
}

void insert(int l, int r, int n, tree* t) {
   if (l > t->r || r < t->l) return;
   if (l <= t->l && r >= t->r) {
      t->occur += n, t->max += n;
      return;
   }
   insert(l, r, n, t->left);
   insert(l, r, n, t->right);
   t->max = (t->left->max > t->right->max ? t->left->max : t->right->max) + t->occur;
}

int find(int l, int r, tree* t) {
   if (l > t->r || r < t->l) return 0;
   if (l <= t->l && r >= t->r) return t->max;
   int lmax = find(l, r, t->left);
   int rmax = find(l, r, t->right);
   return (lmax > rmax ? lmax : rmax) + t->occur;
}

void freetree(tree* t) {
   if (t == NULL) return;
   freetree(t->left);
   freetree(t->right);
   delete t;  
}

int c, s, r;
tree* t;

void init();
void solve();

main() {
   init();
   solve();
   freetree(t);
   return 0;  
}


void init() {
   fin >> c >> s >> r;
   t = newtree(1, c - 1);
   buildtree(1, c - 1, t);   
}

void solve() {
   int i;
   for (i = 0; i < r; i++) {
      int o, d, n;
      fin >> o >> d >> n;
      int max = find(o, d - 1, t);
//      cout << max << ' ' << n << ' ' << s << endl;

      if (n + max <= s) {
         fout << "YES" << endl;
         insert(o, d - 1, n, t);
      }
      else
         fout << "NO" << endl;
   }   
}