SHARE
TWEET

Untitled

a guest Feb 17th, 2017 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. PCMS2 Web Client
  3.  
  4. Information Statements Monitor Submit Runs Messenger Logout
  5.  
  6. Run source
  7.  
  8. Problem E. RMQ2
  9. Attempt 9
  10. Time    10:23:33
  11. Outcome OK
  12. Language    MinGW C++11 4.8
  13. Source
  14. ?
  15. #include <bits/stdc++.h>
  16.  
  17. #define ll long long
  18. #define str string
  19. #define XX first
  20. #define YY second
  21. #define vec vector
  22. #define re return
  23. #define y1 dasfasdf32s23s3224
  24. #define LN '\n'
  25. #define all(a) a.begin(), a.end()
  26. #define in insert
  27. #define pb push_back
  28. #define mp make_pair
  29. #define forn(i, n) for (int i = 0; i < n; i++)
  30. #define form(i, a, b) for (int i = a; i <= b; i++)
  31.  
  32. const int INF = 1e9 + 7;
  33. const ll LINF = 1e18 + 7;
  34. const ll P = 997;
  35. const ll nothing = LINF + 1;
  36. const int MOD = 1e9 + 7;
  37. const int MOD1 = 1e9 + 7;
  38. const int MOD2 = 1e9 + 5;
  39. const bool is_testing = 0;
  40. const int MAXN = 50000;
  41.  
  42. using namespace std;
  43.  
  44. int n, maxk;
  45. ll t[800007], a[100007], p[800007], u[800007];
  46.  
  47. void push(int v)
  48. {
  49.     if (v > maxk)
  50.         return;
  51.     if (u[v] == nothing)
  52.     {
  53.         t[v] += p[v];
  54.         if (u[2 * v + 1] != nothing)
  55.             push(2 * v + 1);
  56.         if (u[2 * v + 2] != nothing)
  57.             push(2 * v + 2);
  58.         p[2 * v + 1] += p[v];
  59.         p[2 * v + 2] += p[v];
  60.         p[v] = 0;
  61.     }
  62.     else
  63.     {
  64.         t[v] = u[v];
  65.         u[2 * v + 1] = u[v];
  66.         u[2 * v + 2] = u[v];
  67.         p[2 * v + 1] = 0;
  68.         p[2 * v + 2] = 0;
  69.         p[v] = 0;
  70.         u[v] = nothing;
  71.     }
  72. }
  73. void build(int v, int vl, int vr)
  74. {
  75.     maxk = max(maxk, v);
  76.     if (vl == vr)
  77.         t[v] = a[vl];
  78.     else
  79.     {
  80.         int vm = (vl + vr) / 2;
  81.         build(v * 2 + 1, vl, vm);
  82.         build(v * 2 + 2, vm + 1, vr);
  83.         t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
  84.     }
  85. }
  86.  
  87. ll get(int v, int vl, int vr, int l, int r)
  88. {
  89.     push(v);
  90.     if (l > vr || r < vl)
  91.         re LINF;
  92.     if (vl >= l && vr <= r)
  93.         re t[v];
  94.     int vm = (vl + vr) / 2;
  95.     ll q1 = get(v * 2 + 1, vl, vm, l, r);
  96.     ll q2 = get(v * 2 + 2, vm + 1, vr, l, r);
  97.     re min(q1, q2);
  98. }
  99.  
  100. void add(int v, int vl, int vr, int l, int r, ll x)
  101. {
  102.     push(v);
  103.     if (vl > r || vr < l)
  104.         return;
  105.     if (vl >= l && vr <= r)
  106.     {
  107.         p[v] += (ll)x;
  108.         push(v);
  109.     }
  110.     else
  111.     {
  112.         int vm = (vl + vr) / 2;
  113.         add(v * 2 + 1, vl, vm, l, r, x);
  114.         add(v * 2 + 2, vm + 1, vr, l, r, x);
  115.         t[v] = min(t[2 * v + 1], t[2 * v + 2]);
  116.     }
  117. }
  118.  
  119. void iz(int v, int vl, int vr, int l, int r, ll x)
  120. {
  121.     push(v);
  122.     if (vr < l || vl > r)
  123.         return;
  124.     if (vl >= l && vr <= r)
  125.     {
  126.         u[v] = x;
  127.         push(v);
  128.     }
  129.     else
  130.     {
  131.         int vm = (vl + vr) / 2;
  132.         iz(v * 2 + 1, vl, vm, l, r, x);
  133.         iz(v * 2 + 2, vm + 1, vr, l, r, x);
  134.         t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
  135.     }
  136. }
  137.  
  138. int main()
  139. {
  140.     ios_base::sync_with_stdio(0);
  141.     cin.tie();
  142.     freopen("rmq2.in", "r", stdin);
  143.     freopen("rmq2.out", "w", stdout);
  144.     if (is_testing)
  145.     {
  146.         freopen("input.txt", "r", stdin);
  147.     }
  148.     cin >> n;
  149.     forn(i, n)
  150.         cin >> a[i];
  151.     forn(i, 800005)
  152.         u[i] = nothing;
  153.     build(0, 0, n - 1);
  154.     str s;
  155.     while(cin >> s)
  156.     {
  157.         if (s == "min")
  158.         {
  159.             int l, r;
  160.             cin >> l >> r;
  161.             l--; r--;
  162.             cout << get(0, 0, n - 1, l, r) << LN;
  163.         }
  164.         else
  165.         if (s == "add")
  166.         {
  167.             ll l, r, x;
  168.             cin >> l >> r >> x;
  169.             l--; r--;
  170.             add(0, 0, n - 1, l, r, x);
  171.         }
  172.         else
  173.         {
  174.             ll l, r, x;
  175.             cin >> l >> r >> x;
  176.             l--; r--;
  177.             iz(0, 0, n - 1, l, r, x);
  178.         }
  179.     /*
  180.     forn(i, 2 * n)
  181.         cout << t[i] << ' ';
  182.     cout << LN;*/
  183.     }
  184. }
RAW Paste Data
Top