Madiyar

Untitled

Nov 14th, 2012
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  21. #define f0(a) memset(a, 0, sizeof(a))
  22. #define all(v) v.begin(), v.end()
  23. #define pii pair<int,int>
  24. #define vi vector<int>
  25.  
  26. #ifdef WIN32
  27.     #define I64 "%I64d"
  28. #else
  29.     #define I64 "%lld"
  30. #endif
  31. const int Max = 100001;
  32. struct query {
  33.     int c, l, r;
  34.     query() {
  35.    
  36.     }
  37.     query(int _c, int _l, int _r) {
  38.         c = _c; l = _l; r = _r;
  39.     }
  40. };
  41. query q1[3000000];
  42. query q2[3000000];          
  43. pii e[3000000];
  44. int dp[Max + 10], ans[3000000];
  45.  
  46. int n, m, en;
  47.  
  48. int main() {
  49.     #ifdef LOCAL
  50.         freopen("in","r",stdin);
  51.         freopen("out","w",stdout);
  52.     #endif  
  53.     scanf("%d", &n);
  54.     for (int i = 0; i < n; ++i) {
  55.         int c, a, b;
  56.         scanf("%d%d%d", &c, &a, &b);
  57.         q1[i] = query(c, a, b);
  58.         e[en++] = mp(a, -(i + 1));
  59.         e[en++] = mp(b, -(i + 1));
  60.     }
  61.     scanf("%d", &m);
  62.     for (int i = 0; i < m; ++i) {
  63.         int mm, k, s;
  64.         scanf("%d%d%d", &mm, &k, &s);
  65.         q2[i] = query(k, mm, s + mm);
  66.         e[en++] = mp(mm, i + 1);
  67.     }
  68.    
  69.     sort(e, e + en);
  70.  
  71.     dp[0] = (1ll << 31) - 1;
  72.     for (int i = 0; i < en; ++i) {
  73.         if (e[i].s > 0) {
  74.             int j = e[i].s - 1;
  75.             ans[j] = (dp[q2[j].c] > q2[j].r);
  76.             continue;
  77.         }
  78.  
  79.         int j = -e[i].s - 1;
  80.        
  81.         if (q1[j].l == e[i].f) {
  82.             for (int i = Max - 1; i >= q1[j].c; --i)
  83.                 dp[i] = max(dp[i], min(dp[i - q1[j].c], q1[j].r));
  84.         } else {
  85.             for (int i = 1; i < Max; ++i)
  86.                 if (dp[i] == e[i].s) dp[i] = 0;
  87.         }
  88.     }
  89.  
  90.     for (int i = 0; i < m; ++i)
  91.         puts(ans[i] ? "TAK" : "NIE");
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment