比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
YGOI_真神名曰驴蛋蛋 |
运行时间 |
0.101 s |
代码语言 |
C++ |
内存使用 |
0.35 MiB |
提交时间 |
2016-08-28 19:03:40 |
显示代码纯文本
- #include<stdio.h>
- #define fo(s) freopen((s),"r",stdin)
- #define fe(s) freopen((s),"w",stdout)
- #define fpstd fclose(stdin);fclose(stdout);
- inline int mid(const int&l,const int&r){return (l+r)>>1;}
- inline int max(const int&a,const int&b){return a<b?b:a;}
- const int MAXN = 60000+10;
- struct Node{
- int val;
- int lazy;
- Node(){val=lazy=0;}
- };
- struct LineTree{
- Node save[MAXN<<2];
- void add(int root,int l,int r,int ansl,int ansr,int val){
- if(ansl<=l&&ansr>=r){
- save[root].val+=val;
- save[root].lazy+=val;
- return ;
- }GetNew(root);
- if(ansl<=mid(l,r))add(root<<1,l,mid(l,r),ansl,ansr,val);
- if(ansr> mid(l,r))add(root<<1|1,mid(l,r)+1,r,ansl,ansr,val);
- save[root].val=max(save[root<<1].val,save[root<<1|1].val);
- }
- int query(int root,int l,int r,int ansl,int ansr){
- if(ansl<=l&&ansr>=r)return save[root].val;
- GetNew(root);
- if(ansr<=mid(l,r))return query(root<<1,l,mid(l,r),ansl,ansr);
- if(ansl> mid(l,r))return query(root<<1|1,mid(l,r)+1,r,ansl,ansr);
- return max(query(root<<1,l,mid(l,r),ansl,ansr),query(root<<1|1,mid(l,r)+1,r,ansl,ansr));
- }
- void GetNew(int root){
- save[root<<1].lazy +=save[root].lazy;
- save[root<<1].val +=save[root].lazy;
- save[root<<1|1].lazy+=save[root].lazy;
- save[root<<1|1].val +=save[root].lazy;
- save[root].lazy =0;
- }
- }a;
- int doing(){
- fo("railway.in");
- fe("railway.out");
- int s,t,k;
- int From,To,Times;
- scanf("%d%d%d",&s,&t,&k);
- for(int i=1;i<=k;++i){
- scanf("%d%d%d",&From,&To,&Times);
- if(a.query(1,1,s-1,From,To-1)+Times<=t){
- printf("YES\n");
- a.add(1,1,s-1,From,To-1,Times);
- }else printf("NO\n");
- }
- fpstd;
- return 0;
- }
- int popopopopopopopopopopopopopo=doing();
- int main(){;}