ccbeginner

CF 52C (TLE)

Feb 27th, 2020
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //CH 52C circular RMQ
  2. /******************************************************************************
  3.  
  4.                               Online C++ Compiler.
  5.                Code, Compile, Run and Debug C++ program online.
  6. Write your code in this editor and press "Run" button to compile and execute it.
  7.  
  8. *******************************************************************************/
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. #define int long long
  13.  
  14. struct node{
  15.     int l, r, mid;
  16.     int val, tag;//val := min val in subtrees, tag := added val
  17.     node *lch, *rch;
  18.     node(int L, int R){
  19.         l = L;
  20.         r = R;
  21.         mid = (L + R) / 2;
  22.         val = tag = 0;
  23.         lch = rch = nullptr;
  24.     }
  25.     void addv(int L, int R, int V){
  26.         //cout << l << ' ' << r << ' ' << L << ' ' << R << ' ' << V << '\n';
  27.         if(L == l && R == r){
  28.             tag += V;
  29.         }else{
  30.             val = 1e15;
  31.             if(L <= mid){
  32.                 if(lch == nullptr)lch = new node(l, mid);
  33.                 lch->addv(L, min(mid, R), V);
  34.             }
  35.             if(R > mid){
  36.                 if(rch == nullptr)rch = new node(mid+1, r);
  37.                 rch->addv(max(mid+1, L), R, V);
  38.             }
  39.             if(lch != nullptr)val = min(val, lch->val+lch->tag);
  40.             if(rch != nullptr)val = min(val, rch->val+rch->tag);
  41.         }
  42.     }
  43.     int getv(int L, int R){
  44.         //cout << l << ' ' << r << ' ' << val << ' ' << tag << ' ' << L << ' ' << R << '\n';
  45.         if(L == l && R == r){
  46.             return val + tag;
  47.         }else{
  48.             int ret = 1e15;
  49.             if(L <= mid){
  50.                 if(lch == nullptr)lch = new node(l, mid);
  51.                 ret = min(ret, lch->getv(L, min(mid, R)));
  52.             }
  53.             if(R > mid){
  54.                 if(rch == nullptr)rch = new node(mid+1, r);
  55.                 ret = min(ret, rch->getv(max(mid+1, L), R));
  56.             }
  57.             return ret + tag;
  58.         }
  59.     }
  60. };
  61.  
  62. int32_t main(){
  63.     int n;
  64.     cin >> n;
  65.     node *root = new node(0, n-1);
  66.     for(int i = 0; i < n; ++i){
  67.         int x;
  68.         cin >> x;
  69.         root->addv(i, i, x);
  70.     }
  71.     int q;
  72.     cin >> q;
  73.     cin.get();
  74.     while(q--){
  75.         string s;
  76.         getline(cin, s);
  77.         stringstream ss;
  78.         ss << s;
  79.         int arr[3];
  80.         int idx = 0;
  81.         while(ss >> arr[idx])++idx;
  82.         if(idx == 2){
  83.             if(arr[0] <= arr[1])cout << root->getv(arr[0], arr[1]) << '\n';
  84.             else cout << min(root->getv(arr[0], n-1), root->getv(0, arr[1])) << '\n';
  85.         }else{
  86.             if(arr[0] <= arr[1])root->addv(arr[0], arr[1], arr[2]);
  87.             else{
  88.                 root->addv(arr[0], n-1, arr[2]);
  89.                 root->addv(0, arr[1], arr[2]);
  90.             }
  91.         }
  92.     }
  93.     return 0;
  94. }
RAW Paste Data