daily pastebin goal
50%
SHARE
TWEET

Untitled

a guest Dec 10th, 2018 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. #define ll long long;
  7.  
  8. using namespace std;
  9.  
  10. const int MOD = 1e9 + 7;
  11. const int p = 7;
  12. const int MAXN = 1e5;
  13. int pw[MAXN];
  14. int h[MAXN];
  15. int power[MAXN];
  16. const int inf = 39489;
  17. int tree[4 * MAXN];
  18. int color[4 * MAXN];
  19. int n;
  20. vector<int> a;
  21.  
  22. void build(int v, int l, int r)
  23. {
  24.     if (l == r)
  25.     {
  26.         tree[v] = (h[l] - h[l - 1] + MOD) % MOD;
  27.         color[v] = -1;
  28.     }
  29.     else
  30.     {
  31.         int m = (l + r) / 2;
  32.         build(v * 2, l, m);
  33.         build(v * 2 + 1, m + 1, r);
  34.         color[v] = -1;
  35.         tree[v] = (tree[v * 2] + tree[v * 2 + 1]) % MOD;
  36.     }
  37. }
  38.  
  39. void push(int v, int l, int r)
  40. {
  41.     if (color[v] == -1)
  42.     {
  43.         return;
  44.     }
  45.     int m = (l + r) / 2;
  46.     tree[v * 2] = (color[v] * (power[m] - power[l - 1] + MOD)) % MOD;
  47.     color[v * 2] = color[v];
  48.     tree[v * 2 + 1] = (color[v] * (power[r] - power[m] + MOD)) % MOD;
  49.     color[v * 2 + 1] = color[v];
  50.     color[v] = -1;
  51. }
  52.  
  53. int get(int l, int r, int tv, int tl, int tr)
  54. {
  55.     if (tr < l || r < tl)
  56.     {
  57.         return inf;
  58.     }
  59.     else if (l <= tl && tr <= r)
  60.     {
  61.         return tree[tv];
  62.     }
  63.     else
  64.     {
  65.         push(tv, tl, tr);
  66.         int tm = (tl + tr) / 2;
  67.         return (get(l, r, tv * 2, tl, tm) + get(l, r, tv * 2 + 1, tm + 1, tr)) % MOD;
  68.     }
  69. }
  70.  
  71. void upd(int l, int r, int x, int tv, int tl, int tr)
  72. {
  73.     if (tr < l || r < tl)
  74.     {
  75.         return;
  76.     }
  77.     else if (l <= tl && tr <= r)
  78.     {
  79.         tree[tv] = (x * (power[tr] - power[tl - 1] + MOD)) % MOD;
  80.         color[tv] = x;
  81.     }
  82.     else
  83.     {
  84.         push(tv, tl, tr);
  85.         int tm = (tl + tr) / 2;
  86.             upd(l, r, x, tv * 2, tl, tm);
  87.         upd(l, r, x, tv * 2 + 1, tm + 1, tr);
  88.         tree[tv] = (tree[tv * 2] + tree[tv * 2 + 1]) % MOD;
  89.     }
  90. }
  91.  
  92. int main()
  93. {
  94.     cin >> n;
  95.     a.resize(n + 1);
  96.     for (int i = 1; i <= n; ++i)
  97.     {
  98.         cin >> a[i];
  99.     }
  100.  
  101.     pw[1] = 1;
  102.     power[1] = 1;
  103.     for (int i = 2; i <= n; ++i)
  104.     {
  105.         pw[i] = (pw[i - 1] * p) % MOD;
  106.         power[i] = (power[i - 1] + pw[i]) % MOD;
  107.     }
  108.  
  109.     h[1] = (a[1] * pw[1]) % MOD;
  110.     for (int i = 2; i <= n; ++i)
  111.     {
  112.         h[i] = (h[i - 1] + (a[i] * pw[i]) % MOD) % MOD;
  113.     }
  114.  
  115.     int q;
  116.     cin >> q;
  117.     for (int i = 0; i < q; ++i)
  118.     {
  119.         int k, l, r, x;
  120.         cin >> k >> l >> r >> x;
  121.         if (k == 0)
  122.         {
  123.             upd(l, r, x, 1, 1, n);
  124.         }
  125.         else
  126.         {
  127.             if (l > r)
  128.             {
  129.                 swap(l, r);
  130.             }
  131.             int m = get(l, l + x - 1, 1, 1, n);
  132.             int g = get(r, r + x - 1, 1, 1, n);
  133.             int kek = r - l;
  134.             cout << "hui ";
  135.             cout << m << " " << g << "\n";
  136.             m = (m * pw[kek]) % MOD;
  137.             cout << "pizda " << m << "\n";
  138.             if (m == g)
  139.             {
  140.                 cout << "+";
  141.             }
  142.             else
  143.             {
  144.                 cout << "-";
  145.             }
  146.         }
  147.     }
  148. }
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