fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ALL(A) A.begin(), A.end()
  4. #define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
  5. #define FORD(i, a, b) for(int i = (a); i >= (int)b; i--)
  6. #define BIT(mask, i) ((mask>>(i))&1)
  7. #define fi first
  8. #define se second
  9. #define file(name)  if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
  10. template <class A, class B> bool mini(A &a, B b)  {if (a > b) {a = b; return 1;} return 0;}
  11. template <class A, class B> bool maxi(A &a, B b)  {if (a < b) {a = b; return 1;} return 0;}
  12. const int oo = (int) 1e9;
  13. const long long INF = (long long) 1e18;
  14. const int N = 4e5 + 5;
  15. const int LG = (int) __lg(N) + 1;
  16.  
  17. int n, m, q;
  18. int a[N];
  19. int L[N], R[N], X[N], Y[N];
  20. struct Queries {
  21.     int p, u, v, id;
  22.  
  23.     bool operator <(const Queries &e) const {
  24.         return p < e.p;
  25.     }
  26. } Q[N];
  27.  
  28. namespace sub1 {
  29.     bool checksub() {
  30.         return max({n, m, q}) <= 5000;
  31.     }
  32.  
  33.     int b[N];
  34.  
  35.     void solve() {
  36.         FOR(t, 1, q) {
  37.             int p = Q[t].p, u = Q[t].u, v = Q[t].v;
  38.             b[p] = a[p];
  39.  
  40.             FOR(i, u, v) if(L[i] <= p && p <= R[i] && b[p] == X[i]) {
  41.                 b[p] = X[i] + Y[i];
  42.             }
  43.  
  44.             cout << b[p] << "\n";
  45.         }
  46.     }
  47. }
  48.  
  49. namespace sub2 {
  50.     bool checksub() {
  51.         FOR(i, 1, m) {
  52.             if(L[i] != 1 || R[i] != n) return 0;
  53.         }
  54.         FOR(i, 1, q) {
  55.             if(Q[i].u != 1 || Q[i].v != m) return 0;
  56.         }
  57.         return 1;
  58.     }
  59.  
  60.     int ans[N];
  61.     map <int, vector <int>> val;
  62.  
  63.     void solve() {
  64.         FOR(i, 1, m) val[X[i]].push_back(i);
  65.  
  66.         FOR(i, 1, n) {
  67.             int cur = a[i];
  68.             int j = 0;
  69.  
  70.             while(j <= m) {
  71.                 int nej = upper_bound(ALL(val[cur]), j) - val[cur].begin();
  72.                 if(nej == val[cur].size()) break;
  73.  
  74.                 int ind = val[cur][nej];
  75.  
  76.                 cur+= Y[ind];
  77.                 j = ind;
  78.             }
  79.  
  80.             ans[i] = cur;
  81.         }
  82.  
  83.         FOR(i, 1, q) cout << ans[Q[i].p] << "\n";
  84.     }
  85. }
  86.  
  87. namespace sub3 {
  88.     bool checksub() {
  89.         if(max(n, m) > 10000) return 0;
  90.         FOR(i, 1, m) if(L[i] != 1 || R[i] != n) return 0;
  91.         return 1;
  92.     }
  93.  
  94.     vector <int> pos[N];
  95.     int last[N];
  96.     int nxt[N][LG];
  97.  
  98.     void prep() {
  99.         FOR(i, 1, m) pos[X[i]].push_back(i);
  100.         FOR(i, 1, (int)1e5) pos[i].push_back(m + 1);
  101.  
  102.         memset(last, 0x3f, sizeof last);
  103.  
  104.         FORD(i, m, 1) {
  105.             nxt[i][0] = last[X[i] + Y[i]];
  106.             last[X[i]] = i;
  107.         }
  108.  
  109.         for(int j = 1; (1 << j) <= m; j++) FOR(i, 1, m) {
  110.             if(nxt[i][j - 1] > m) nxt[i][j] = oo;
  111.             else if(nxt[nxt[i][j - 1]][j - 1] > m) nxt[i][j] = oo;
  112.             else nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
  113.         }
  114.     }
  115.  
  116.     void solve() {
  117.         prep();
  118.  
  119.         FOR(i, 1, q) {
  120.             int p = Q[i].p, u = Q[i].u, v = Q[i].v;
  121.             int res = a[p];
  122.  
  123.             int l = pos[res][lower_bound(ALL(pos[res]), u) - pos[res].begin()];
  124.  
  125.             if(l <= v) {
  126.                 res = X[l] + Y[l];
  127.  
  128.                 int z = __lg(m);
  129.                 FORD(s, z, 0) if(nxt[l][s] <= v) {
  130.                     l = nxt[l][s];
  131.                     res = X[l] + Y[l];
  132.                 }
  133.             }
  134.  
  135.             cout << res << "\n";
  136.         }
  137.     }
  138. }
  139.  
  140. namespace sub5 {
  141.     struct Ope {
  142.         int x, y, l, r, id;
  143.         bool operator <(const Ope &e) const {
  144.             return l < e.l;
  145.         }
  146.     } ope[N];
  147.     const int BLOCK = 320;
  148.  
  149.     struct Events {
  150.         int k, pos, y;
  151.         bool operator <(const Events &e) const {
  152.             return k < e.k;
  153.         }
  154.     } events[N];
  155.  
  156.     int cnt = 0;
  157.     pair <int, int> val[N];
  158.  
  159.     int f[BLOCK + 5][(int)1e5 + 5];
  160.  
  161.     void prep() {
  162.         FOR(i, 1, m) {
  163.             events[++ cnt] = {ope[i].l, i, ope[i].y};
  164.             events[++ cnt] = {ope[i].r + 1, i, 0};
  165.             val[i].first = ope[i].x;
  166.         }
  167.  
  168.         sort(Q + 1, Q + 1 + q);
  169.         sort(events + 1, events + 1 + cnt);
  170.  
  171.         FOR(i, 0, BLOCK) FOR(v, 1, (int)1e5) f[i][v] = v;
  172.     }
  173.  
  174.     inline void update(int pos, int y) {
  175.         val[pos].se = y;
  176.  
  177.         int b = pos / BLOCK;
  178.         int L = b * BLOCK, R = min(m, (b + 1) * BLOCK) - 1;
  179.  
  180.         FOR(i, L, R) f[b][val[i].fi] = val[i].fi;
  181.  
  182.         FORD(i, R, L) {
  183.             int x = val[i].fi, tmp = val[i].se;
  184.             f[b][x] = f[b][x + tmp];
  185.         }
  186.     }
  187.  
  188.     inline int query(int pos, int l, int r) {
  189.         int res = a[pos];
  190.         int bl = l / BLOCK, br = r / BLOCK;
  191.         if(bl == br) {
  192.             FOR(i, l, r) if(val[i].fi == res) res+= val[i].se;
  193.         } else {
  194.             FOR(i, l, (bl + 1) * BLOCK - 1) if(val[i].fi == res) res+= val[i].se;
  195.             FOR(i, bl + 1, br - 1) res = f[i][res];
  196.             FOR(i, br * BLOCK, r) if(val[i].fi == res) res+= val[i].se;
  197.         }
  198.         return res;
  199.     }
  200.  
  201.     int ans[N];
  202.  
  203.     void solve() {
  204.         FOR(i, 1, m) ope[i] = {X[i], Y[i], L[i], R[i], i};
  205.         prep();
  206.  
  207.         int j = 1;
  208.         FOR(i, 1, q) {
  209.             int p = Q[i].p, u = Q[i].u, v = Q[i].v;
  210.  
  211.             while(j <= cnt && events[j].k <= p) {
  212.                 update(events[j].pos, events[j].y);
  213.                 j++;
  214.             }
  215.  
  216.             ans[Q[i].id] = query(p, u, v);
  217.         }
  218.  
  219.         FOR(i, 1, q) cout << ans[i] << "\n";
  220.     }
  221. }
  222.  
  223. void process() {
  224.     cin >> n >> m;
  225.     FOR(i, 1, n) cin >> a[i];
  226.     FOR(i, 1, m) cin >> L[i] >> R[i] >> X[i] >> Y[i];
  227.     cin >> q;
  228.     FOR(i, 1, q) cin >> Q[i].p >> Q[i].u >> Q[i].v, Q[i].id = i;
  229.  
  230.     // if(sub1::checksub()) return sub1::solve();
  231.     // if(sub2::checksub()) return sub2::solve();
  232.     // if(sub3::checksub()) return sub3::solve();
  233.     return sub5::solve();
  234. }
  235.  
  236. signed main() {
  237.     ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
  238.     file("cquery");
  239.     process();
  240.     return (0 ^ 0);
  241. }
  242.  
Success #stdin #stdout 0.04s 142868KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jnAm8q
language:
C++14 (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!