比赛 Segment Tree Competition 评测结果 AAAAAAAAAAAA
题目名称 售票系统 最终得分 100
用户昵称 YGOI_真神名曰驴蛋蛋 运行时间 0.101 s
代码语言 C++ 内存使用 0.35 MiB
提交时间 2016-08-28 19:03:40
显示代码纯文本
  1. #include<stdio.h>
  2. #define fo(s) freopen((s),"r",stdin)
  3. #define fe(s) freopen((s),"w",stdout)
  4. #define fpstd fclose(stdin);fclose(stdout);
  5. inline int mid(const int&l,const int&r){return (l+r)>>1;}
  6. inline int max(const int&a,const int&b){return a<b?b:a;}
  7. const int MAXN = 60000+10;
  8. struct Node{
  9. int val;
  10. int lazy;
  11. Node(){val=lazy=0;}
  12. };
  13. struct LineTree{
  14. Node save[MAXN<<2];
  15. void add(int root,int l,int r,int ansl,int ansr,int val){
  16. if(ansl<=l&&ansr>=r){
  17. save[root].val+=val;
  18. save[root].lazy+=val;
  19. return ;
  20. }GetNew(root);
  21. if(ansl<=mid(l,r))add(root<<1,l,mid(l,r),ansl,ansr,val);
  22. if(ansr> mid(l,r))add(root<<1|1,mid(l,r)+1,r,ansl,ansr,val);
  23. save[root].val=max(save[root<<1].val,save[root<<1|1].val);
  24. }
  25. int query(int root,int l,int r,int ansl,int ansr){
  26. if(ansl<=l&&ansr>=r)return save[root].val;
  27. GetNew(root);
  28. if(ansr<=mid(l,r))return query(root<<1,l,mid(l,r),ansl,ansr);
  29. if(ansl> mid(l,r))return query(root<<1|1,mid(l,r)+1,r,ansl,ansr);
  30. return max(query(root<<1,l,mid(l,r),ansl,ansr),query(root<<1|1,mid(l,r)+1,r,ansl,ansr));
  31. }
  32. void GetNew(int root){
  33. save[root<<1].lazy +=save[root].lazy;
  34. save[root<<1].val +=save[root].lazy;
  35. save[root<<1|1].lazy+=save[root].lazy;
  36. save[root<<1|1].val +=save[root].lazy;
  37. save[root].lazy =0;
  38. }
  39. }a;
  40. int doing(){
  41. fo("railway.in");
  42. fe("railway.out");
  43. int s,t,k;
  44. int From,To,Times;
  45. scanf("%d%d%d",&s,&t,&k);
  46. for(int i=1;i<=k;++i){
  47. scanf("%d%d%d",&From,&To,&Times);
  48. if(a.query(1,1,s-1,From,To-1)+Times<=t){
  49. printf("YES\n");
  50. a.add(1,1,s-1,From,To-1,Times);
  51. }else printf("NO\n");
  52. }
  53. fpstd;
  54. return 0;
  55. }
  56. int popopopopopopopopopopopopopo=doing();
  57. int main(){;}