比赛 |
区间问题练习 |
评测结果 |
WWEEWWWEWWTA |
题目名称 |
售票系统 |
最终得分 |
8 |
用户昵称 |
swttc |
运行时间 |
1.291 s |
代码语言 |
C++ |
内存使用 |
1.47 MiB |
提交时间 |
2017-04-21 20:34:18 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF=200000000;
int c,s,r,minv[121000],tic[61000],o1,d,n,addv[121000],minn;
void build(int o,int x,int y)
{
if(x==y) minv[o]=tic[x];
else
{
int lc=o*2,rc=lc+1,m=x+(y-x)/2;
build(lc,x,m);
build(rc,m+1,y);
minv[o]=min(minv[lc],minv[rc]);
}
return;
}
void query(int o,int x,int y,int addo=0)
{
if(x>=o1&&y<=d) minn=min(minn,minv[o]+addv[o]+addo);
else
{
int lc=o*2,rc=lc+1,m=x+(y-x)/2;
if(m>=o1) query(lc,x,m,addv[o]+addo);
if(m<d) query(rc,m+1,y,addv[o]+addo);
}
return;
}
void upit(int o,int x,int y)
{
if(y>x)
{
int lc=o*2,rc=lc+1;
minv[o]=min(minv[lc],minv[rc]);
}
minv[o]+=addv[o];
return;
}
void add(int o,int x,int y)
{
if(x==y) addv[o]=-n;
else
{
int lc=o*2,rc=lc+1,m=x+(y-x)/2;
if(m>=o) add(lc,x,m);
if(m<d) add(rc,m+1,y);
}
upit(o,x,y);
return;
}
int main()
{
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
scanf("%d%d%d",&c,&s,&r);
for(int i=1;i<=c;i++) tic[i]=s;
build(1,1,c);
for(int i=1;i<=r;i++)
{
scanf("%d%d%d",&o1,&d,&n);
minn=INF;
query(1,1,c);
if(minn>=n)
{
printf("YES\n");
//cout<<"minn"<<minn<<endl;
//for(int j=1;j<=c*2+1;j++) cout<<"minv[j]"<<minv[j]<<endl;
add(1,o1,d);
}
else printf("NO\n");
}
return 0;
}