| 题目名称 | 247. 售票系统 |
|---|---|
| 输入输出 | railway.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 12 |
| 题目来源 |
 BYVoid
于2008-12-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：468， 提交：1629， 通过率：28.73% | ||||
 AAAAAAAAAA |
100 | 0.043 s | 0.72 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.065 s | 2.14 MiB | C++ |
 dateri |
100 | 0.066 s | 0.35 MiB | C++ |
 sansui666 |
100 | 0.067 s | 0.89 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 0.071 s | 0.88 MiB | C++ |
 Pine |
100 | 0.076 s | 0.87 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.076 s | 1.70 MiB | C++ |
|
eason_wu |
100 | 0.077 s | 19.68 MiB | C++ |
 _IOSTREAM_ |
100 | 0.081 s | 2.25 MiB | C++ |
 Foenix |
100 | 0.082 s | 1.00 MiB | C++ |
| 本题关联比赛 | |||
| 20100324 | |||
| Segment Tree Competition | |||
| 区间问题练习 | |||
| 数据结构练习 | |||
| 关于 售票系统 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
注意没有第3站到第3站的车票！！！
| ||||
|
简单的线段树？
| ||||
|
生活常识坑倒一切……
夜莺
2021-07-20 11:26
50楼
| ||||
|
<p>asd</p>
 oier12345
2019-10-06 13:25
49楼
| ||||
|
#include<stdio.h>
#include <algorithm> #include <iostream> using namespace std; class _______ {public: int _,__; }_[240010]; int __,___,____,_____,______,_______,________; int _L_(){ int _________=0,__________=1;char ___________=getchar(); while(___________<'0'||___________>'9'){ if(___________=='-') __________=-1; ___________=getchar(); } while(___________>='0'&&___________<='9'){ _________=_________*10+___________-48; ___________=getchar(); } return _________*__________; } inline void pushdown(int _Y_) { if(_[_Y_].__) { _[_Y_<<1]._+=_[_Y_].__; _[_Y_<<1|1]._+=_[_Y_].__; _[_Y_<<1].__+=_[_Y_].__; _[_Y_<<1|1].__+=_[_Y_].__; _[_Y_].__=0; } } int query(int _Y_,int _________,int ____) { if(_________>=_____&&____<=______) return _[_Y_]._; int mid=(_________+____)>>1,now=0; pushdown(_Y_); if(_____<=mid) now=max(now,query(_Y_<<1,_________,mid)); if(mid<______) now=max(now,query(_Y_<<1|1,mid+1,____)); return now; } void add(int _Y_,int _________,int ____) { if(_________>=_____&&____<=______){ _[_Y_]._+=_______,_[_Y_].__+=_______;return;} int mid=(_________+____)>>1; pushdown(_Y_); if(_____<=mid) add(_Y_<<1,_________,mid); if(mid<______) add(_Y_<<1|1,mid+1,____); _[_Y_]._=max(_[_Y_<<1]._,_[_Y_<<1|1]._); } int lyh() { freopen("railway.in","r",stdin); freopen("railway.out","w",stdout); __=_L_()-1; ___=_L_(); ____=_L_(); for(________=1;________<=____;________++) { _____=_L_(); ______=_L_()-1; _______=_L_(); if(___-query(1,1,__)>=_______){ printf("YES\n"); add(1,1,__); } else printf("NO\n"); } return 0; } int Main=lyh(); int main(){;} | ||||
|
| ||||
|
唉 没注意楼上各位仁兄提醒啊~~~
| ||||
|
又练习一发分块
 CSU_Turkey
2017-09-05 17:22
45楼
| ||||
|
说好的模板题交了n次...
建树的时候不是1—n而是1——n-1 查询的时候也有点小小的细节 | ||||
|
好气
CSU_Turkey
2017-09-05 16:41
43楼
| ||||
-1
WHZ0325【问题描述】
某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票， 即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数。售票 系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序，实现这个自动售票系统。
【输入格式】
第一行包含三个用空格隔开的整数C、S和R，其中1≤C≤60000， l≤S≤60000，1≤R≤60000。C为城市个数，S为列车上的座位数，R为所有售票申请总数。接下来的R行每行为一个售票申请，用三个由空格隔开的整数O，D和N表示，O为起始站，D 为目的地站，N为车票张数，其中1≤O<D≤C，所有的售票申请按申请的时间从早到晚给出。
【输出格式】
输出共有R行，每行输出一个“YES”或“NO”，表示当前的售票申请被受理或不被受理。
【输入样例】
4 6 4 1 4 2 1 3 2 2 4 3 1 2 3
【输出样例】
YES YES NO NO