|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: kol
|
Author: Tomasz Waleń
|
| I stage contest |
Byteotian State Railways decided to keep up with the times and introduce to their offer an InterCity connection. Because of lack of efficient engines, clean carriages and straight tracks it was possible to establish only one such a connection. The lack of any computer system for seat reservation was another obstacle. Writing the main part of this system is your task.
For simplicity we assume that the InterCity connection runs through c cities numbered successively from 1 to c (the starting city has the number 1, and c is the number of the ending city). There are s seats in the train and transporting more passengers between any two successive stations is not allowed.
The computer system is to receive successive requests and determine whether they may be fulfilled. A request is accepted when in the given section of the railway line there is enough vacant seats in the train. Otherwise it is rejected. Partial accepting of a request is not allowed, e.g. for a part of a route or for less passengers. After accepting a request, the number of vacant seats in the train is updated. The requests are processed successively in the order of coming.
Task
Write a program which:
- reads from the text file kol.in the description of the connection and a list of requested reservations,
- computes which requests will be accepted, and which will be rejected,
- writes to the text file kol.out the answers to all the requests.
Input
In the first line of the text file kol.in there are three integers c, s and r (1<=c<=60 000, 1<=s<=60 000, 1<=r<=60 000) separated by single spaces. The numbers denote respectively: the number of cities on the railway line, the number of seats in the train, and the number of requests. In the following r lines there are consecutive requests written. In the line of number i+1 there is the i-th request described. The description consists of three integers o, d and n (1<=o<d<=c, 1<=n<=s) separated by single spaces. They denote: the number of the station of origin, the number of the destination station and the requested number of seats, respectively.
Output
Your program should write r lines to the text file kol.out. In the i-th line there should be exactly one character:
- T (for “yes”) – if the i-th request is accepted,
- N (for “no”) – otherwise.
Solution
又是一道线段树。挖个坑先 ^_^
终于过了……反复不过竟然是因为数据用的太小了（unsigned short），后来改成long就AC了……一直觉得应该没问题啊，结果还是溢出了。看来像unsigned啊、short啊这种关键字还是慎用为妙。
从这个题可以学到线段树通过标记来减少不必要修改的思想——其实上一道zju的就是这样的。
代码：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cassert>
using namespace std;
FILE *fin = fopen("kol.in","r"),
*fout = fopen("kol.out","w");
const long A=1,B=60000;
long C,S,R;//城市数目、座位总数、请求数
struct STNode{
long a,b,lch,rch,avail,sold;
STNode(long _a, long _b){
a=_a;
b=_b;
avail=S;
sold=0;
lch=rch=0;
}
STNode(void){}
}STree[(B-A)<<1];
void ST_Build(long a, long b){
static unsigned i=1;
unsigned now=i++;
STree[now]=STNode(a,b);
if(b-a>1){
STree[now].lch=i;
ST_Build(a,(a+b)>>1);
STree[now].rch=i;
ST_Build((a+b)>>1,b);
}
}
void ST_Clear(long i){ //清空节点i的sold域
if(i==0) return;
STree[STree[i].lch].sold+=STree[i].sold;
STree[STree[i].rch].sold+=STree[i].sold;
STree[i].avail-=STree[i].sold;
STree[i].sold=0;
}
bool ST_Check(long a, long b, long s, long i){
if(STree[i].sold>0) ST_Clear(i);
if(a<=STree[i].a&&STree[i].b<=b) return (STree[i].avail>=s);
else{
bool flag1=true,flag2=true;
if(a<((STree[i].a+STree[i].b)>>1)) flag1=ST_Check(a,b,s,STree[i].lch);
if(b>((STree[i].a+STree[i].b)>>1)) flag2=ST_Check(a,b,s,STree[i].rch);
return (flag1&&flag2);
}
}
void ST_Delete(long a,long b, long s, long i){
if(STree[i].sold>0) ST_Clear(i);
if(a<=STree[i].a&&STree[i].b<=b){
assert(STree[i].avail>=s);
STree[i].avail-=s;
STree[STree[i].lch].sold+=s;
STree[STree[i].rch].sold+=s;
}else{
if(a<((STree[i].a+STree[i].b)>>1)) ST_Delete(a,b,s,STree[i].lch);
else ST_Clear(STree[i].lch);
if(b>((STree[i].a+STree[i].b)>>1)) ST_Delete(a,b,s,STree[i].rch);
else ST_Clear(STree[i].rch);
STree[i].avail=min(STree[STree[i].lch].avail,STree[STree[i].rch].avail);
}
}
int main()
{
fscanf(fin,"%d %d %d\n",&C,&S,&R);
ST_Build(A,B);
for(int r=0,o,d,n;r<R;r++){
fscanf(fin,"%d %d %d\n",&o,&d,&n);
if(ST_Check(o,d,n,1)){
fprintf(fout,"T\n");
ST_Delete(o,d,n,1);
}else fprintf(fout,"N\n");
}
fclose(fin);
fclose(fout);
return 0;
}
P.S.不知道是不是我rp用完了，反正现在cena也不给我好好干活了。只要测pas的程序一律显示“崩溃（访问无效内存）”，重装cena、fp都没用，郁闷。就搞了两个评测系统，一个是HWD的，感觉很烦琐，不知道怎么评测C的程序；一个就是这个雅礼ZYF的系统，直接评测exe，好像不支持交互。下面是此程序生成的成绩单，我比标程慢……
成绩单
编号： standard； 总得分： 130； 总耗时： 1.21
试题名称： Problem A； 测试例数： 13； 本题得分： 130.0； 本题耗时： 1.21
例号 用时 评测结果 得分 1 0.02 正确 10 2 0.02 正确 10 3 0.02 正确 10 4 0.02 正确 10 5 0.02 正确 10 6 0.36 正确 10 7 0.03 正确 10 8 0.08 正确 10 9 0.02 正确 10 10 0.09 正确 10 11 0.11 正确 10 12 0.03 正确 10 13 0.39 正确 10
编号： tomtung； 总得分： 130； 总耗时： 1.61
试题名称： Problem A； 测试例数： 13； 本题得分： 130.0； 本题耗时： 1.61
例号 用时 评测结果 得分 1 0.03 正确 10 2 0.03 正确 10 3 0.03 正确 10 4 0.03 正确 10 5 0.03 正确 10 6 0.44 正确 10 7 0.05 正确 10 8 0.09 正确 10 9 0.09 正确 10 10 0.09 正确 10 11 0.16 正确 10 12 0.06 正确 10 13 0.48 正确 10
最近评论