API tools faq
paste
Advertisement
prog3r

B (On segment on segment) AC 734ms

prog3r
Jun 30th, 2025
425
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.30 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("Ofast,unroll-loops")
  4. signed main() {
  5.     ios::sync_with_stdio(0);
  6.     cin.tie(0);
  7.     int n, q;
  8.     cin >> n >> q;
  9.     int g1, g2;
  10.     cin >> g1 >> g2;
  11.     struct Node {
  12.         int val=0;
  13.         int l=-1;
  14.         int r=-1;
  15.         int move_to_y; // -5 means that it is y node already
  16.     };
  17.     vector<Node> nodes;
  18.     nodes.reserve(6e7);
  19.     auto l = [&] (int u) -> int {
  20.         return (u == -1)?-1:nodes[u].l;
  21.     };
  22.     auto r = [&] (int u) -> int {
  23.         return (u == -1)?-1:nodes[u].r;
  24.     };
  25.     auto gtval = [&] (int u) -> int {
  26.         return (u == -1)?0:nodes[u].val;
  27.     };
  28.     auto mky = [&] (int val, int l, int r) -> int {
  29.         nodes.push_back({val, l, r, -5});
  30.         return nodes.size()-1;
  31.     };
  32.     auto mkx = [&] (int val, int l, int r, int move_to_y) -> int {
  33.         nodes.push_back({val, l, r, move_to_y});
  34.         return nodes.size()-1;
  35.     };
  36.     auto move_to_y = [&] (int u) -> int {
  37.         return (u==-1)?-1:nodes[u].move_to_y;
  38.     };
  39.     auto incy = [&] (auto f, int u, int ytl, int ytr, int y, int val) -> int {
  40.         if (ytl == ytr) {
  41.             return mky(gtval(u) + val, -1, -1);
  42.         } else {
  43.             int tm = (ytl + ytr) >> 1;
  44.             if (y <= tm) {
  45.                 int nwl = f(f, l(u), ytl, tm, y, val);
  46.                 return mky(gtval(nwl)+gtval(r(u)), nwl, r(u));
  47.             } else {
  48.                 int nwr = f(f, r(u), tm+1, ytr, y, val);
  49.                 return mky(gtval(l(u))+gtval(nwr), l(u), nwr);
  50.             }
  51.         }
  52.     };
  53.     auto incx = [&] (auto f, int u, int xtl, int xtr, int ytl, int ytr, int x, int y, int val) -> int {
  54.         if (xtl == xtr) {
  55.             int goy = incy(incy, move_to_y(u), ytl, ytr, y, val);
  56.             return mkx(gtval(goy), -1, -1, goy);
  57.         }
  58.         int tm = (xtl + xtr) >> 1;
  59.         int L = l(u), R = r(u);
  60.         if (x <= tm) {
  61.             L = f(f, l(u), xtl, tm, ytl, ytr, x, y, val);
  62.         } else {
  63.             R = f(f, r(u), tm+1, xtr, ytl, ytr, x, y, val);
  64.         }
  65.         int goy = incy(incy, move_to_y(u), ytl, ytr, y, val);
  66.         return mkx(gtval(L)+gtval(R), L, R, goy);
  67.     };
  68.     auto gt_prev_val = [&] (auto f, int u, int xtl, int xtr, int ytl, int ytr, int x) -> int {
  69.         if (xtl == xtr) {
  70.             if (nodes[u].move_to_y != -5) {
  71.                 u = nodes[u].move_to_y;
  72.             }
  73.             if (ytl == ytr) {
  74.                 return ytl;
  75.             } else {
  76.                 int tm = (ytl + ytr) >> 1;
  77.                 if (gtval(l(u))) {
  78.                     return f(f, l(u), xtl, xtr, ytl, tm, x);
  79.                 }
  80.                 return f(f, r(u), xtl, xtr, tm+1, ytr, x);
  81.             }
  82.         } else {
  83.             int tm = (xtl + xtr) >> 1;
  84.             if (x <= tm) {
  85.                 return f(f, l(u), xtl, tm, ytl, ytr, x);
  86.             } else {
  87.                 return f(f, r(u), tm+1, xtr, ytl, ytr, x);
  88.             }
  89.         }
  90.     };
  91.     auto gt = [&] (auto f, int u, int xtl, int xtr, int ytl, int ytr, int xl, int xr, int yl, int yr) -> int {
  92.         if (u == -1) {
  93.             return 0ll;
  94.         }
  95.         if (xtl == xl && xtr == xr) {
  96.             if (nodes[u].move_to_y != -5) {
  97.                 u = nodes[u].move_to_y;
  98.             }
  99.             if (ytl == yl && ytr == yr) {
  100.                 return gtval(u);
  101.             } else {
  102.                 int tm = (ytl + ytr) >> 1;
  103.                 int ret = 0;
  104.                 if (yl <= tm) {
  105.                     ret += f(f, l(u), xtl, xtr, ytl, tm, xl, xr, yl, min(yr, tm));
  106.                 }
  107.                 if (yr >= tm+1) {
  108.                     ret += f(f, r(u), xtl, xtr, tm+1, ytr, xl, xr, max(yl, tm+1), yr);
  109.                 }
  110.                 return ret;
  111.             }
  112.         } else {
  113.             int tm = (xtl + xtr) >> 1;
  114.             int ret = 0;
  115.             if (xl <= tm) {
  116.                 ret += f(f, l(u), xtl, tm, ytl, ytr, xl, min(xr, tm), yl, yr);
  117.             }
  118.             if (xr >= tm+1) {
  119.                 ret += f(f, r(u), tm+1, xtr, ytl, ytr, max(xl, tm+1), xr, yl, yr);
  120.             }
  121.             return ret;
  122.         }
  123.     };
  124.     vector<int> roots(q+1, -1);
  125.     for (int i = 1; i <= n; i += 1) {
  126.         roots[0] = incx(incx, roots[0], 1, n, 0, min(n, 100), i, 0, 1);
  127.     }
  128.     int ra = 0;
  129.     auto gen = [&] () -> int {
  130.         (ra = g1*ra+g2) %= n;
  131.         return ra;
  132.     };
  133.     for (int i = 1; i <= q; i += 1) {
  134.         int tp, from;
  135.         cin >> tp >> from;
  136.         roots[i] = roots[from];
  137.         if (tp == 1) {
  138.             int idx, val;
  139.             cin >> idx >> val;
  140.             int prev_val = gt_prev_val(gt_prev_val, roots[i], 1, n, 0, min(n, 100), idx);
  141.             roots[i] = incx(incx, roots[i], 1, n, 0, min(n, 100), idx, prev_val, -1);
  142.             roots[i] = incx(incx, roots[i], 1, n, 0, min(n, 100), idx, val, 1);
  143.         }
  144.         if (tp == 2) {
  145.             int valL, valR;
  146.             cin >> valL >> valR;
  147.             int iL = gen()+1;
  148.             int iR = gen()+1;
  149.             if (!(iL <= iR)) {
  150.                 swap(iL, iR);
  151.             }
  152.             int ans = gt(gt, roots[i], 1, n, 0, min(n, 100), iL, iR, valL, valR);
  153.             cout << ans << "\n";
  154.             g1 += ans;
  155.             if (g1 >= n) {
  156.                 g1 -= n;
  157.             }
  158.         }
  159.     }
  160. }
  161. ;;;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!