Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <ctime>
- #include <cassert>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define all(v) v.begin(), v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- const int Max = 100001;
- struct query {
- int c, l, r;
- query() {
- }
- query(int _c, int _l, int _r) {
- c = _c; l = _l; r = _r;
- }
- };
- query q1[3000000];
- query q2[3000000];
- pii e[3000000];
- int dp[Max + 10], ans[3000000];
- int n, m, en;
- int main() {
- #ifdef LOCAL
- freopen("in","r",stdin);
- freopen("out","w",stdout);
- #endif
- scanf("%d", &n);
- for (int i = 0; i < n; ++i) {
- int c, a, b;
- scanf("%d%d%d", &c, &a, &b);
- q1[i] = query(c, a, b);
- e[en++] = mp(a, -(i + 1));
- e[en++] = mp(b, -(i + 1));
- }
- scanf("%d", &m);
- for (int i = 0; i < m; ++i) {
- int mm, k, s;
- scanf("%d%d%d", &mm, &k, &s);
- q2[i] = query(k, mm, s + mm);
- e[en++] = mp(mm, i + 1);
- }
- sort(e, e + en);
- dp[0] = (1ll << 31) - 1;
- for (int i = 0; i < en; ++i) {
- if (e[i].s > 0) {
- int j = e[i].s - 1;
- ans[j] = (dp[q2[j].c] > q2[j].r);
- continue;
- }
- int j = -e[i].s - 1;
- if (q1[j].l == e[i].f) {
- for (int i = Max - 1; i >= q1[j].c; --i)
- dp[i] = max(dp[i], min(dp[i - q1[j].c], q1[j].r));
- } else {
- for (int i = 1; i < Max; ++i)
- if (dp[i] == e[i].s) dp[i] = 0;
- }
- }
- for (int i = 0; i < m; ++i)
- puts(ans[i] ? "TAK" : "NIE");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment