Advertisement
erek1e

POI Task Cards

Jul 27th, 2022
729
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <tuple>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 1e9;
  9.  
  10. struct Segment {
  11.     int l[2], r[2]; // l are start values, r are corresponding min end values
  12.     Segment () {}
  13.     Segment (int x, int y) {
  14.         l[0] = r[0] = x;
  15.         l[1] = r[1] = y;
  16.     }
  17.     Segment (int l0, int l1, int r0, int r1) {
  18.         l[0] = l0;
  19.         l[1] = l1;
  20.         r[0] = r0;
  21.         r[1] = r1;
  22.     }
  23. };
  24. struct Node {
  25.     Segment s;
  26.     Node * left, * right;
  27. };
  28. Segment combine(Segment a, Segment b) {
  29.     Segment s(a.l[0], a.l[1], INF, INF);
  30.     if (a.r[0] <= b.l[0]) s.r[0] = b.r[0];
  31.     else if (a.r[0] <= b.l[1]) s.r[0] = b.r[1];
  32.     if (a.r[1] <= b.l[0]) s.r[1] = b.r[0];
  33.     else if (a.r[1] <= b.l[1]) s.r[1] = b.r[1];
  34.     return s;
  35. }
  36. Segment combine(Node * &a, Node * &b) {
  37.     assert(a || b);
  38.     if (!a) return b->s;
  39.     if (!b) return a->s;
  40.     return combine(a->s, b->s);
  41. }
  42. void update(Node * &base, int l, int r, int i, int x, int y) {
  43.     if (l+1 == r) {
  44.         base->s = {x, y};
  45.         return;
  46.     }
  47.     int m = (l + r) / 2;
  48.     if (i < m) {
  49.         if (!base->left) base->left = new Node();
  50.         update(base->left, l, m, i, x, y);
  51.     } else {
  52.         if (!base->right) base->right = new Node();
  53.         update(base->right, m, r, i, x, y);
  54.     }
  55.     base->s = combine(base->left, base->right);
  56. }
  57. bool queryPossible(Node * &root) {
  58.     return root->s.r[0] != INF;
  59. }
  60.  
  61. int main() {
  62.     int n; cin >> n;
  63.     Node * root = new Node();
  64.     vector<int> x(n), y(n);
  65.     for (int i = 0; i < n; ++i) {
  66.         cin >> x[i] >> y[i];
  67.         if (x[i] > y[i]) swap(x[i], y[i]);
  68.         update(root, 0, n, i, x[i], y[i]);
  69.     }
  70.     int q; cin >> q;
  71.     while (q--) {
  72.         int a, b; cin >> a >> b;
  73.         --a, --b;
  74.         swap(x[a], x[b]);
  75.         swap(y[a], y[b]);
  76.         update(root, 0, n, a, x[a], y[a]);
  77.         update(root, 0, n, b, x[b], y[b]);
  78.         cout << (queryPossible(root) ? "TAK" : "NIE") << '\n';
  79.     }
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement