CEOI售票系统

描述 Description

某次列车途经C个城市,城市编号依次为1到C,列车上共有S个座位,铁路局规定售出的车票只能是坐票, 即车上所有的旅客都有座。售票系统是由计算机执行的,每一个售票申请包含三个参数,分别用O、D、N表示,O为起始站,D为目的地站,N为车票张数。售票 系统对该售票申请作出受理或不受理的决定,只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序,实现这个自动 售票系统。

输入格式 Input Format

第一行包含三个用空格隔开的整数C、S和R,其中$1≤C≤60000$, $l≤S≤60000$,$1≤R≤60000$。C为城市个数,S为列车上的座位数,R为所有售票申请总数。接下来的R行每行为一个售票申请,用三个由空格隔开的整数O,D和N表示,O为起始站,D 为目的地站,N为车票张数,其中$1≤D≤C$,$1≤O≤C$,所有的售票申请按申请的时间从早到晚给出。

输出格式 Output Format

输出共有R行,每行输出一个“YES”或“NO”,表示当前的售票申请被受理或不被受理。

样例输入 Sample Input

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

样例输出 Sample Output

YES
YES
NO
NO

题解

这道题也很好思考,对每个数据先updata然后search,如果返回的值大于座位数,那么就把刚刚的票取消,即updata的偏移量,记录值为负数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 60100
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define INF -200000000
using namespace std;
int n,s,k;
int ax,ay,x,y,t;
struct qaq{
int maxx;
int delta;
}tree[maxn*4];
bool flag;

int findit(int l,int r,int root){
    int mid,tl,tr;
    if(x>r||y<l) return INF;
if(x<=l&&r<=y) return tree[root].maxx;
mid=(l+r)>>1;
int temp=tree[root].delta;
tree[L(root)].delta+=temp;
tree[L(root)].maxx+=temp;
tree[R(root)].maxx+=temp;
tree[R(root)].delta+=temp;
tree[root].delta=0;
tl=findit(l,mid,L(root));
tr=findit(mid+1,r,R(root));
return max(tl,tr);
}

void updatait(int l,int r,int root){
int mid;
if(x>r||y<l) return;
if(x<=l&&r<=y){
tree[root].maxx+=t;
tree[root].delta+=t;
return;
}
int temp=tree[root].delta;
tree[L(root)].delta+=temp;
tree[L(root)].maxx+=temp;
tree[R(root)].maxx+=temp;
tree[R(root)].delta+=temp;
tree[root].delta=0;
mid=(l+r)>>1;
updatait(l,mid,L(root));
updatait(mid+1,r,R(root));
tree[root].maxx=max(tree[L(root)].maxx,tree[R(root)].maxx);
}

int main(){
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
memset(tree,0,sizeof(tree));
cin>>n>>s>>k;
for(int i=1;i<=k;i++){
flag=1;
scanf("%d%d%d",&ax,&ay,&t);
x=ax;
y=ay-1;
updatait(1,n,1);
int ans=findit(1,n,1);
if(ans<=s) cout<<"YES"<<endl;
else{
cout<<"NO"<<endl;
t=-t;
updatait(1,n,1);
}
}
return 0;
}