xZiLing 2021-08-05 10:56:24 阅读数:672
A train runs on C Between two cities ( The departure city number is 1, The number of the city reached at the end is C), Suppose the train has S A seat , Now there is R Booking business . Now I want to know about this R This transaction is processed , See which reservations can meet , What can't be satisfied .
A reservation is made by O、D、N Three integers , From the starting station O To the target station D Need to book N A seat . A reservation can be satisfied means that there are empty seats within the travel range of the business , Otherwise, you can't meet . A business cannot be split , That is, the starting point and terminal cannot be changed , The number of reserved seats cannot be changed . All scheduled requirements are processed in the order given .
Please write a program , Look at those reservations that can meet , Those who can't meet .
Input file The first line in the three integers C、S、R,(1<=c<=60 000, 1<=s<=60 000, 1<=r<=60 000) They are separated by a space . Next R Each line has three integers O、D、N,(1<=o<d<=c, 1<=n<=s), Represents each scheduled business separately .
Right. I This business , If it can satisfy , In the output file in Of the I Line output “T”, Otherwise output “N”
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
T
T
N
N
This is a water problem with pits
The segment tree maintains the minimum value of the interval ,
You can't check and subtract , It is possible that the front meets the requirements , Less , The back doesn't meet the requirements
So if you judge to be satisfied , reduce , Otherwise, it will not be reduced
pit ::: Order from l To r, The actual operation interval should be [l,r-1], Because I got off at the target station , Don't occupy a seat
#include<cstdio> #include<algorithm> #define N 60001 using namespace std; int n,m,opl,opr,w,q; bool ok; class tree { private: struct node { int l,r,minn,f; }tr[N*4]; public: void build(int k,int l,int r) { tr[k].l=l;tr[k].r=r; if(l==r) { tr[k].minn=m; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tr[k].minn=min(tr[k<<1].minn,tr[k<<1|1].minn); } void down(int k) { tr[k<<1].minn-=tr[k].f; tr[k<<1|1].minn-=tr[k].f; tr[k<<1].f+=tr[k].f; tr[k<<1|1].f+=tr[k].f; tr[k].f=0; } void solve(int k,int g) { if(tr[k].l>=opl&&tr[k].r<=opr) { if(g==1) { if(tr[k].minn<w) ok=true; } else { tr[k].minn-=w; tr[k].f+=w; } return; } if(tr[k].f) down(k); int mid=tr[k].l+tr[k].r>>1; if(opl<=mid) solve(k<<1,g); if(opr>mid) solve(k<<1|1,g); if(g==2) tr[k].minn=min(tr[k<<1].minn,tr[k<<1|1].minn); } }t; int main() { scanf("%d%d%d",&n,&m,&q); t.build(1,1,n); for(int i=1;i<=q;i++) { ok=false; scanf("%d%d%d",&opl,&opr,&w); opr--; t.solve(1,1); if(ok) puts("N"); else { puts("T"); t.solve(1,2); } } return 0; }
版权声明:本文为[xZiLing]所创,转载请带上原文链接,感谢。 https://car.inotgo.com/2021/08/20210805105356155V.html