#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e4;
int c, s, r;
int a[N + 5], tree[(N + 5) << 1], lzytag[(N + 5) << 1];
int ls(int x) { return x << 1;}
int rs(int x) { return x << 1 | 1;}
void pushup(int x) {
tree[x] = max(tree[ls(x)], tree[rs(x)]);
}
void addtag(int x, int xl, int xr, int val) {
lzytag[x] += val;
tree[x] += val;
}
void pushdown(int x, int xl, int xr) {
if(lzytag[x] != 0) {
int mid = (xl + xr) >> 1;
addtag(ls(x), xl, mid, lzytag[x]); addtag(rs(x), mid + 1, xr, lzytag[x]);
lzytag[x] = 0;
}
}
void update(int l, int r, int x, int xl, int xr, int val) {
if (l <= xl && xr <= r) {
addtag(x, xl, xr, val);
return ;
}
pushdown(x, xl, xr);
int mid = (xl + xr) >> 1;
if (l <= mid) update(l, r, ls(x), xl, mid, val);
if (r > mid) update(l, r, rs(x), mid + 1, xr, val);
pushup(x);
}
signed main() {
cin >> c >> s >> r;
while (r--) {
int o, d, n;
cin >> o >> d >> n;
update(o, d - 1, 1, 1, c, n);
if (tree[1] > s) {
update(o, d - 1, 1, 1, c, -n);
cout << "N\n";
} else cout << "T\n";
}
return 0;
}
P8856 [POI 2002] 火车线路
题目描述
某列火车从 1 号城市出发，前往编号为 C 的城市。该火车有 S 个座位，现在有 R 个车票订购需求。
一个订购由 O,D,N 三个整数组成，表示从起点站 O 到目标站 D 需要订购 N 个座位。
如果在该订购范围内有能满足的空座位，就称该订购可以被满足，否则就不可以。
请你按订购给出顺序处理，判断是否可以满足该订购需求。
输入格式
第一行为三个整数 C,S,R。
接下来 R 行，每行为三个整数 O,D,N，分别表示每一个预定。
输出格式
对第 i 个预定，如果能满足，输出 T，否则输出 N。
输入输出样例 #1
输入 #1
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
输出 #1
T
T
N
N
说明/提示
数据范围：1 \le C,S,R \le 60000。
