fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  10. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  11. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  12. #define fi first
  13. #define se second
  14. #define M 1000000000
  15. #define MAXN 500001
  16. #define INF (1ll<<30)
  17. #define BLOCK_SIZE 425
  18. #define MAX_NODE 1001001
  19. #define LOG 19
  20. #define ALPHA_SIZE 26
  21. #define BASE 311
  22. #define NAME "file"
  23. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  24. using namespace std;
  25. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  26. const ll NMOD = 1;
  27. const int dx[] = {-1, 0, 1,0};
  28. const int dy[] = {0, 1, 0, -1};
  29. //**Variable**//
  30. ll n,R, Q,   cur_ver =0, cnt_ver = 0  ;
  31. ll last = 0 ;
  32. ll arr[MAXN] ;
  33. ll root[MAXN] ;
  34. //**Struct**//
  35. struct Query {
  36.     ll r, a, b, c,d ;
  37. };
  38. vector<Query> que ;
  39. struct Node {
  40.     ll left, right, val ;
  41. };
  42. struct Persistent_seg {
  43.     Node tree[MAXN *20]  ;
  44.     ll cur_node = 0 ;
  45.     int build( ll l, ll r ) {
  46.         ll id =  ++ cur_node;
  47.         if(l == r ) {
  48.             tree[cur_node].val = arr[l] ;
  49.             return id;
  50.         }
  51.           ll m = (l + r) >> 1;
  52.         tree[id].left = build(l, m  ) ;
  53.         tree[id].right = build(m + 1, r) ;
  54.         tree[id].val = max( tree[tree[id].left].val, tree[tree[id].right].val ) ;
  55.         return id ;
  56.     }
  57.     int update(ll pre_node, ll l, ll r, ll pos, ll value ) {
  58.         ll id = ++ cur_node ;
  59.         tree[id] = tree[pre_node] ;
  60.         if(l == r ) {
  61.             tree[id].val = value ;
  62.             return id;
  63.         }
  64.        ll m = (l + r) >> 1;
  65.         if(m >= pos ) tree[id].left = update(tree[pre_node].left, l, m, pos, value) ;
  66.         else tree[id].right = update(tree[pre_node].right, m + 1, r,pos, value) ;
  67.         tree[id].val =max( tree[tree[id].left].val, tree[tree[id].right].val ) ;
  68.         return id ;
  69.     }
  70.     ll get(ll id, ll l, ll r, ll u, ll v ) {
  71.         if(u >r || v < l ) return -INF;
  72.         if(u <= l && v >= r ) return tree[id].val ;
  73.           ll m = (l + r) >> 1;
  74.         return max(get(tree[id].left, l, m, u, v ), get(tree[id].right, m + 1, r, u, v ) ) ;
  75.     }
  76. } seg ;
  77. //**Function**//
  78. template<class X, class Y >
  79. bool minimize(X & x, const Y &y ) {
  80.     return x > y ? x = y, 1:0 ;
  81. }
  82. template<class X, class Y >
  83. bool maximize(X &x, const Y &y ) {
  84.     return x < y ? x = y, 1:0 ;
  85. }
  86.  
  87. void init() {
  88.     cin>>n;
  89.     FOR(i,1,n) cin >> arr[i];
  90.     root[0] = seg.build(1, n) ;
  91. //    FOR(i , 1 , n ) cout <<seg.get(root[0] , 1 , n , i , i ) << " "; cout <<"run " << el ;
  92.     cin >> R >> Q;
  93. }
  94.  
  95. void solve() {
  96.     FOR(i, 1, Q) {
  97.         ll r, a, b, c, d;
  98.         cin >> r >> a >> b >> c >> d;
  99.         que.push_back({r, a, b, c, d});
  100.     }
  101.     FOR(i, 1, R) {
  102.         ll cntttt =  0 ;
  103.         for (auto [t, a, b, c, d] : que) {
  104. //                cntttt ++ ;
  105.             if (t == 1) {
  106.                 ll u = (1LL * last * a + c) % n + 1;
  107.                 ll k = (1LL * last * b + d) % M + 1 ;
  108. //                cout << u << " " << k << el ;
  109.                 cnt_ver++;
  110.                 root[cnt_ver] = seg.update(root[cur_ver], 1, n, u, k);
  111.                 cur_ver = cnt_ver;
  112.             } else if (t == 2) {
  113.                 ll u = (1LL * last * a + c) % n + 1;
  114.                 ll v = (1LL * last * b + d) % n + 1;
  115.                 if (u > v) swap(u, v);
  116.                 last = seg.get(root[cur_ver], 1, n, u, v);
  117.                 cout << last << el;
  118.             } else if (t == 3) {
  119.                 ll u = (1LL * last * a + c) % (cnt_ver + 1);
  120.                 cnt_ver++;
  121.                 root[cnt_ver] = root[u];
  122.                 cur_ver = cnt_ver;
  123.             }
  124. //        if(cntttt == 1 )break ;
  125.         }
  126.     }
  127. //       FOR(i , 1 , n ) cout <<seg.get(root[1] , 1 , n , i , i ) << " "; cout <<"run " << el ;
  128. }
  129.  
  130.  
  131. __ROOT__ {
  132. //     freopen(NAME".inp" , "r" , stdin);
  133. //     freopen(NAME".out" , "w", stdout) ;
  134.     fast;
  135.     int t =1 ;//    cin >> t;
  136.     while(t-- ) {
  137.         init();
  138.         solve();
  139.     }
  140. }
  141.  
Success #stdin #stdout 0.01s 7764KB
comments (?)
stdin
copy 
5
4 3 7 2 6
1 8
1 3 0 0 1
2 2 0 0 9
3 3 0 0 1
2 2 0 0 9
3 0 0 1 0
2 0 0 1 3
3 0 0 2 0
2 0 0 3 1
stdout
copy 
7
6
7
7
https://ideone.com/wiwDKe
language:
C++14 (clang 8.0)
created:
176 days ago
visibility:
secret

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!