SHARE
TWEET

Untitled

a guest Mar 13th, 2019 800 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Code for problem E by cookiedoth
  4. Generated 23 Feb 2019 at 02.32 P
  5.  
  6.  
  7. ▅███████ ]▄▄▄▄▄▄▄
  8. █████████▅▄▃
  9. Il████████████████]
  10. ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤
  11.  
  12. ~_^
  13. =_=
  14. ¯\_(ツ)_/¯
  15.  
  16. */
  17.  
  18. #include <iostream>
  19. #include <fstream>
  20. #include <vector>
  21. #include <set>
  22. #include <map>
  23. #include <bitset>
  24. #include <algorithm>
  25. #include <iomanip>
  26. #include <cmath>
  27. #include <ctime>
  28. #include <functional>
  29. #include <unordered_set>
  30. #include <unordered_map>
  31. #include <string>
  32. #include <queue>
  33. #include <deque>
  34. #include <stack>
  35. #include <complex>
  36. #include <cassert>
  37. #include <random>
  38. #include <cstring>
  39. #include <numeric>
  40. #define ll long long
  41. #define ld long double
  42. #define null NULL
  43. #define all(a) a.begin(), a.end()
  44. #define debug(a) cerr << #a << " = " << a << endl
  45. #define forn(i, n) for (int i = 0; i < n; ++i)
  46. #define sz(a) (int)a.size()
  47.  
  48. using namespace std;
  49.  
  50. template<class T> int chkmax(T &a, T b) {
  51.     if (b > a) {
  52.         a = b;
  53.         return 1;
  54.     }
  55.     return 0;
  56. }
  57.  
  58. template<class T> int chkmin(T &a, T b) {
  59.     if (b < a) {
  60.         a = b;
  61.         return 1;
  62.     }
  63.     return 0;
  64. }
  65.  
  66. template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
  67.     while (begin != end) {
  68.         out << (*begin) << " ";
  69.         begin++;
  70.     }
  71.     out << endl;
  72. }
  73.  
  74. template<class T> void output(T x, ostream& out = cerr) {
  75.     output(x.begin(), x.end(), out);
  76. }
  77.  
  78. void fast_io() {
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     cout.tie(0);
  82. }
  83.  
  84. const ll DEFAULT = -1e18;
  85.  
  86. struct st {
  87.     vector<ll> t, len, sum, add_mod, set_mod;
  88.     int n;
  89.  
  90.     void build(vector<ll> &a, int v, int tl, int tr) {
  91.         if (tl == tr) {
  92.             t[v] = sum[v] = a[tl];
  93.             len[v] = 1;
  94.         }
  95.         else {
  96.             int tm = (tl + tr) >> 1;
  97.             build(a, v * 2, tl, tm);
  98.             build(a, v * 2 + 1, tm + 1, tr);
  99.             t[v] = max(t[v * 2], t[v * 2 + 1]);
  100.             sum[v] = sum[v * 2] + sum[v * 2 + 1];
  101.             len[v] = (tr - tl + 1);
  102.         }
  103.     }
  104.  
  105.     st(vector<ll> &a) {
  106.         n = a.size();
  107.         t.resize(4 * n);
  108.         sum.resize(4 * n);
  109.         add_mod.resize(4 * n);
  110.         set_mod.resize(4 * n, DEFAULT);
  111.         len.resize(4 * n);
  112.         build(a, 1, 0, n - 1);
  113.     }
  114.  
  115.     st() {}
  116.  
  117.     void apply_add_mod(int v, ll val) {
  118.         if (set_mod[v] != DEFAULT) {
  119.             set_mod[v] += val;
  120.         }
  121.         else {
  122.             add_mod[v] += val;
  123.         }
  124.     }
  125.  
  126.     void apply_set_mod(int v, ll val) {
  127.         add_mod[v] = 0;
  128.         set_mod[v] = val;
  129.     }
  130.  
  131.     void push(int v) {
  132.         assert(add_mod[v] == 0 || set_mod[v] == DEFAULT);
  133.         if (add_mod[v]) {
  134.             t[v] += add_mod[v];
  135.             sum[v] += add_mod[v] * len[v];
  136.             apply_add_mod(v * 2, add_mod[v]);
  137.             apply_add_mod(v * 2 + 1, add_mod[v]);
  138.             add_mod[v] = 0;
  139.         }
  140.         if (set_mod[v] != DEFAULT) {
  141.             t[v] = set_mod[v];
  142.             sum[v] = set_mod[v] * len[v];
  143.             apply_set_mod(v * 2, set_mod[v]);
  144.             apply_set_mod(v * 2 + 1, set_mod[v]);
  145.             set_mod[v] = DEFAULT;
  146.         }
  147.     }
  148.  
  149.     ll get_sum(int v) {
  150.         if (set_mod[v] != DEFAULT) {
  151.             return set_mod[v] * len[v];
  152.         }
  153.         if (add_mod[v]) {
  154.             return add_mod[v] * len[v] + sum[v];
  155.         }
  156.         return sum[v];
  157.     }
  158.  
  159.     ll get_t(int v) {
  160.         if (set_mod[v] != DEFAULT) {
  161.             return set_mod[v];
  162.         }
  163.         if (add_mod[v]) {
  164.             return add_mod[v] + t[v];
  165.         }
  166.         return t[v];
  167.     }
  168.  
  169.     void recalc(int v) {
  170.         t[v] = max(get_t(v * 2), get_t(v * 2 + 1));
  171.         sum[v] = get_sum(v * 2) + get_sum(v * 2 + 1);
  172.     }
  173.  
  174.     void add_update(int l, int r, ll val, int v, int tl, int tr) {
  175.         if (l > r) {
  176.             return;
  177.         }
  178.         if (l == tl && r == tr) {
  179.             apply_add_mod(v, val);
  180.             return;
  181.         }
  182.         int tm = (tl + tr) >> 1;
  183.         push(v);
  184.         add_update(l, min(r, tm), val, v * 2, tl, tm);
  185.         add_update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);
  186.         recalc(v);
  187.     }
  188.  
  189.     void set_update(int l, int r, ll val, int v, int tl, int tr) {
  190.         if (l > r) {
  191.             return;
  192.         }
  193.         if (l == tl && r == tr) {
  194.             apply_set_mod(v, val);
  195.             return;
  196.         }
  197.         int tm = (tl + tr) >> 1;
  198.         push(v);
  199.         set_update(l, min(r, tm), val, v * 2, tl, tm);
  200.         set_update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);
  201.         recalc(v);
  202.     }
  203.  
  204.     ll get_sum(int l, int r, int v, int tl, int tr) {
  205.         if (l > r) {
  206.             return 0;
  207.         }
  208.         if (l == tl && r == tr) {
  209.             return get_sum(v);
  210.         }
  211.         int tm = (tl + tr) >> 1;
  212.         push(v);
  213.         ll res_l = get_sum(l, min(r, tm), v * 2, tl, tm);
  214.         ll res_r = get_sum(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
  215.         return res_l + res_r;
  216.     }
  217.  
  218.     int lower_bound(ll val, int v, int tl, int tr) {
  219.         if (tl == tr) {
  220.             return tl;
  221.         }
  222.         push(v);
  223.         int tm = (tl + tr) >> 1;
  224.         if (get_t(v * 2) >= val) {
  225.             return lower_bound(val, v * 2, tl, tm);
  226.         }
  227.         else {
  228.             return lower_bound(val, v * 2 + 1, tm + 1, tr);
  229.         }
  230.     }
  231.  
  232.     //interface
  233.  
  234.     void add_update(int l, int r, ll val) {
  235.         add_update(l, r, val, 1, 0, n - 1);
  236.     }
  237.  
  238.     void set_update(int l, int r, ll val) {
  239.         set_update(l, r, val, 1, 0, n - 1);
  240.     }
  241.  
  242.     ll get_sum(int l, int r) {
  243.         ll res = get_sum(l, r, 1, 0, n - 1);
  244.         return res;
  245.     }
  246.  
  247.     int lower_bound(ll val) {
  248.         if (get_t(1) < val) {
  249.             return n;
  250.         }
  251.         else {
  252.             return lower_bound(val, 1, 0, n - 1);
  253.         }
  254.     }
  255. };
  256.  
  257. int n;
  258. vector<ll> a, k, prefK, b;
  259.  
  260. signed main() {
  261.     fast_io();
  262.    
  263.     cin >> n;
  264.     a.resize(n);
  265.     k.resize(n - 1);
  266.     prefK.resize(n);
  267.     for (int i = 0; i < n; ++i) {
  268.         cin >> a[i];
  269.     }
  270.     for (int i = 0; i < n - 1; ++i) {
  271.         cin >> k[i];
  272.     }
  273.     for (int i = 1; i < n; ++i) {
  274.         prefK[i] = prefK[i - 1] + k[i - 1];
  275.     }
  276.  
  277.     b.resize(n);
  278.     for (int i = 0; i < n; ++i) {
  279.         b[i] = a[i] - prefK[i];
  280.     }
  281.     st t(b), t1(prefK);
  282.  
  283.     int q;
  284.     cin >> q;
  285.     for (int i = 0; i < q; ++i) {
  286.         char type;
  287.         cin >> type;
  288.         if (type == 's') {
  289.             int l, r;
  290.             cin >> l >> r;
  291.             l--;
  292.             r--;
  293.             cout << t.get_sum(l, r) + t1.get_sum(l, r) << '\n';
  294.         }
  295.         if (type == '+') {
  296.             int pos;
  297.             ll val;
  298.             cin >> pos >> val;
  299.             pos--;
  300.             val += t.get_sum(pos, pos);
  301.             int pos1 = t.lower_bound(val);
  302.             t.set_update(pos, pos1 - 1, val);
  303.         }
  304.     }
  305. }
RAW Paste Data
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
Top