fork download 
  1. ll sq_f(ll x) {
  2.     long double r = sqrt((long double)x);
  3.     ll y = (ll)r;
  4.     while ((y + 1) > 0 && (y + 1) * (y + 1) <= x) ++y;
  5.     while (y * y > x) --y;
  6.     return y;
  7. }
  8.  
  9. // 1-based indexing
  10. struct Lazy_Segment_Tree {
  11.     struct Node {
  12.         ll val, lazy, mn, mx;
  13.         Node(ll _val = 0, ll _lazy = 0, ll _mn = 0, ll _mx = 0) : val(_val), lazy(_lazy), mn(_mn), mx(_mx) {}
  14.         Node operator=(ll _val) {
  15.             val = _val;
  16.             lazy = 0;
  17.             mn = mx = 0;
  18.             return *this;
  19.         }
  20.     };
  21.  
  22.     int size, n;
  23.     vector<Node> tree;
  24.     vector<vector<ll>> pref;
  25.  
  26.     void init(int n_) {
  27.         n = n_;
  28.         size = 1;
  29.         while (size < n) size *= 2;
  30.         tree.assign(2 * size + 5, Node());
  31.         pref.resize(6);
  32.         for (int s = 0; s < 6; s++) pref[s].assign(size + 1, 0);
  33.     }
  34.  
  35.     Node merge(const Node &a, const Node &b) {
  36.         Node res;
  37.         res.val = a.val + b.val;
  38.         res.lazy = 0;
  39.         res.mn = min(a.mn, b.mn);
  40.         res.mx = max(a.mx, b.mx);
  41.         return res;
  42.     }
  43.  
  44.     ll range_stage_sum(int s, int l, int r) {
  45.         return pref[s][r] - pref[s][l - 1];
  46.     }
  47.  
  48.     void apply(int idx, int lx, int rx, ll delta) {
  49.         tree[idx].mn += delta;
  50.         tree[idx].mx += delta;
  51.         tree[idx].lazy += delta;
  52.  
  53.         if (tree[idx].mn < 0) tree[idx].mn = 0;
  54.         if (tree[idx].mx < 0) tree[idx].mx = 0;
  55.  
  56.         if (tree[idx].mn >= 5) {
  57.             tree[idx].val = (rx - lx + 1);
  58.             return;
  59.         }
  60.         if (tree[idx].mn == tree[idx].mx) {
  61.             int stage = (int)tree[idx].mn;
  62.             if (stage > 5) stage = 5;
  63.             tree[idx].val = range_stage_sum(stage, lx, rx);
  64.         }
  65.     }
  66.  
  67.     void push(int idx, int lx, int rx) {
  68.         if (tree[idx].lazy == 0) return;
  69.         if (lx != rx) {
  70.             int mx = (lx + rx) / 2;
  71.             apply(2 * idx, lx, mx, tree[idx].lazy);
  72.             apply(2 * idx + 1, mx + 1, rx, tree[idx].lazy);
  73.         }
  74.         tree[idx].lazy = 0;
  75.     }
  76.  
  77.     void build(int idx, int lx, int rx) {
  78.         tree[idx].lazy = 0;
  79.         if (lx == rx) {
  80.             tree[idx].mn = tree[idx].mx = 0;
  81.             tree[idx].val = (lx <= n ? range_stage_sum(0, lx, rx) : 0);
  82.             return;
  83.         }
  84.         int mx = (lx + rx) / 2;
  85.         build(2 * idx, lx, mx);
  86.         build(2 * idx + 1, mx + 1, rx);
  87.         tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
  88.     }
  89.  
  90.     void build(const vector<vector<ll>> &vals) {
  91.         for (int s = 0; s < 6; s++) pref[s][0] = 0;
  92.         for (int i = 1; i <= size; i++) {
  93.             for (int s = 0; s < 6; s++) {
  94.                 pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
  95.             }
  96.         }
  97.         build(1, 1, size);
  98.     }
  99.  
  100.     void update(int l, int r, ll v, int idx, int lx, int rx) {
  101.         if (rx < l || lx > r) return;
  102.  
  103.         if (l <= lx && rx <= r) {
  104.             if (tree[idx].mn == tree[idx].mx) {
  105.                 apply(idx, lx, rx, v);
  106.                 return;
  107.             }
  108.             if (tree[idx].mn + v >= 5) {
  109.                 apply(idx, lx, rx, v);
  110.                 return;
  111.             }
  112.         }
  113.  
  114.         if (lx == rx) {
  115.             apply(idx, lx, rx, v);
  116.             if (tree[idx].mn >= 5) tree[idx].val = 1;
  117.             else tree[idx].val = range_stage_sum((int)tree[idx].mn, lx, rx);
  118.             return;
  119.         }
  120.  
  121.         push(idx, lx, rx);
  122.         int mx = (lx + rx) / 2;
  123.         update(l, r, v, 2 * idx, lx, mx);
  124.         update(l, r, v, 2 * idx + 1, mx + 1, rx);
  125.         tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
  126.     }
  127.  
  128.     void update(int l, int r, ll v) { update(l, r, v, 1, 1, size); }
  129.  
  130.     ll query(int l, int r, int idx, int lx, int rx) {
  131.         if (rx < l || lx > r) return 0;
  132.  
  133.         if (l <= lx && rx <= r) {
  134.             if (tree[idx].mn >= 5) return (rx - lx + 1);
  135.             if (tree[idx].mn == tree[idx].mx) {
  136.                 int stage = (int)tree[idx].mn;
  137.                 if (stage > 5) stage = 5;
  138.                 return range_stage_sum(stage, lx, rx);
  139.             }
  140.         }
  141.  
  142.         if (lx == rx) {
  143.             if (tree[idx].mn >= 5) return 1;
  144.             int stage = (int)tree[idx].mn;
  145.             if (stage > 5) stage = 5;
  146.             return range_stage_sum(stage, lx, rx);
  147.         }
  148.  
  149.         push(idx, lx, rx);
  150.         int mx = (lx + rx) / 2;
  151.         return query(l, r, 2 * idx, lx, mx) + query(l, r, 2 * idx + 1, mx + 1, rx);
  152.     }
  153.  
  154.     ll query(int l, int r) { return query(l, r, 1, 1, size); }
  155. };
  156.  
  157. void solve() {
  158.     int n;
  159.     cin >> n;
  160.     vector<ll> a(n + 1);
  161.     for (int i = 1; i <= n; i++) cin >> a[i];
  162.  
  163.     vector<vector<ll>> vals(6);
  164.     for (int s = 0; s < 6; s++) vals[s].assign(n + 1, 0);
  165.  
  166.     for (int i = 1; i <= n; i++) {
  167.         vals[0][i] = a[i];
  168.         for (int s = 1; s < 6; s++) vals[s][i] = sq_f(vals[s - 1][i]);
  169.     }
  170.  
  171.     Lazy_Segment_Tree st;
  172.     st.init(n);
  173.     st.build(vals);
  174.  
  175.     int q;
  176.     cin >> q;
  177.     while (q--) {
  178.         int type;
  179.         cin >> type;
  180.         if (type == 1) {
  181.             int l, r;
  182.             cin >> l >> r;
  183.             st.update(l, r, 1);
  184.         } else if (type == 2) {
  185.             int l, r, k;
  186.             cin >> l >> r >> k;
  187.             st.update(l, r, -k);
  188.         } else {
  189.             int l, r;
  190.             cin >> l >> r;
  191.             cout << st.query(l, r) << endl;
  192.         }
  193.     }
  194. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:1:1: error: ‘ll’ does not name a type
 ll sq_f(ll x) {
 ^~
prog.cpp:12:9: error: ‘ll’ does not name a type
         ll val, lazy, mn, mx;
         ^~
prog.cpp:13:16: error: expected ‘)’ before ‘_val’
         Node(ll _val = 0, ll _lazy = 0, ll _mn = 0, ll _mx = 0) : val(_val), lazy(_lazy), mn(_mn), mx(_mx) {}
             ~  ^~~~~
                )
prog.cpp:14:24: error: ‘ll’ has not been declared
         Node operator=(ll _val) {
                        ^~
prog.cpp:23:5: error: ‘vector’ does not name a type
     vector<Node> tree;
     ^~~~~~
prog.cpp:24:5: error: ‘vector’ does not name a type
     vector<vector<ll>> pref;
     ^~~~~~
prog.cpp:44:5: error: ‘ll’ does not name a type
     ll range_stage_sum(int s, int l, int r) {
     ^~
prog.cpp:48:41: error: ‘ll’ has not been declared
     void apply(int idx, int lx, int rx, ll delta) {
                                         ^~
prog.cpp:90:22: error: ‘vector’ does not name a type
     void build(const vector<vector<ll>> &vals) {
                      ^~~~~~
prog.cpp:90:28: error: expected ‘,’ or ‘...’ before ‘<’ token
     void build(const vector<vector<ll>> &vals) {
                            ^
prog.cpp:100:31: error: ‘ll’ has not been declared
     void update(int l, int r, ll v, int idx, int lx, int rx) {
                               ^~
prog.cpp:128:31: error: ‘ll’ has not been declared
     void update(int l, int r, ll v) { update(l, r, v, 1, 1, size); }
                               ^~
prog.cpp:130:5: error: ‘ll’ does not name a type
     ll query(int l, int r, int idx, int lx, int rx) {
     ^~
prog.cpp:154:5: error: ‘ll’ does not name a type
     ll query(int l, int r) { return query(l, r, 1, 1, size); }
     ^~
prog.cpp: In member function ‘Lazy_Segment_Tree::Node Lazy_Segment_Tree::Node::operator=(int)’:
prog.cpp:15:13: error: ‘val’ was not declared in this scope
             val = _val;
             ^~~
prog.cpp:15:13: note: suggested alternative: ‘_val’
             val = _val;
             ^~~
             _val
prog.cpp:16:13: error: ‘lazy’ was not declared in this scope
             lazy = 0;
             ^~~~
prog.cpp:17:13: error: ‘mn’ was not declared in this scope
             mn = mx = 0;
             ^~
prog.cpp:17:13: note: suggested alternative: ‘n’
             mn = mx = 0;
             ^~
             n
prog.cpp:17:18: error: ‘mx’ was not declared in this scope
             mn = mx = 0;
                  ^~
prog.cpp: In member function ‘void Lazy_Segment_Tree::init(int)’:
prog.cpp:30:9: error: ‘tree’ was not declared in this scope
         tree.assign(2 * size + 5, Node());
         ^~~~
prog.cpp:31:9: error: ‘pref’ was not declared in this scope
         pref.resize(6);
         ^~~~
prog.cpp: In member function ‘Lazy_Segment_Tree::Node Lazy_Segment_Tree::merge(const Lazy_Segment_Tree::Node&, const Lazy_Segment_Tree::Node&)’:
prog.cpp:37:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
             ^~~
prog.cpp:37:21: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
                     ^~~
prog.cpp:37:29: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
                             ^~~
prog.cpp:38:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘lazy’
         res.lazy = 0;
             ^~~~
prog.cpp:39:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
             ^~
prog.cpp:39:24: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
                        ^~
prog.cpp:39:30: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
                              ^~
prog.cpp:39:18: error: ‘min’ was not declared in this scope
         res.mn = min(a.mn, b.mn);
                  ^~~
prog.cpp:40:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
             ^~
prog.cpp:40:24: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
                        ^~
prog.cpp:40:30: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
                              ^~
prog.cpp:40:18: error: ‘max’ was not declared in this scope
         res.mx = max(a.mx, b.mx);
                  ^~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::apply(int, int, int, int)’:
prog.cpp:49:9: error: ‘tree’ was not declared in this scope
         tree[idx].mn += delta;
         ^~~~
prog.cpp:63:29: error: ‘range_stage_sum’ was not declared in this scope
             tree[idx].val = range_stage_sum(stage, lx, rx);
                             ^~~~~~~~~~~~~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::push(int, int, int)’:
prog.cpp:68:13: error: ‘tree’ was not declared in this scope
         if (tree[idx].lazy == 0) return;
             ^~~~
prog.cpp:71:36: error: ‘tree’ was not declared in this scope
             apply(2 * idx, lx, mx, tree[idx].lazy);
                                    ^~~~
prog.cpp:74:9: error: ‘tree’ was not declared in this scope
         tree[idx].lazy = 0;
         ^~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::build(int, int, int)’:
prog.cpp:78:9: error: ‘tree’ was not declared in this scope
         tree[idx].lazy = 0;
         ^~~~
prog.cpp:81:40: error: ‘range_stage_sum’ was not declared in this scope
             tree[idx].val = (lx <= n ? range_stage_sum(0, lx, rx) : 0);
                                        ^~~~~~~~~~~~~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::build(int)’:
prog.cpp:91:37: error: ‘pref’ was not declared in this scope
         for (int s = 0; s < 6; s++) pref[s][0] = 0;
                                     ^~~~
prog.cpp:94:17: error: ‘pref’ was not declared in this scope
                 pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
                 ^~~~
prog.cpp:94:57: error: ‘vals’ was not declared in this scope
                 pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
                                                         ^~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::update(int, int, int, int, int, int)’:
prog.cpp:104:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn == tree[idx].mx) {
                 ^~~~
prog.cpp:108:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn + v >= 5) {
                 ^~~~
prog.cpp:116:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn >= 5) tree[idx].val = 1;
                 ^~~~
prog.cpp:117:34: error: ‘range_stage_sum’ was not declared in this scope
             else tree[idx].val = range_stage_sum((int)tree[idx].mn, lx, rx);
                                  ^~~~~~~~~~~~~~~
prog.cpp:125:9: error: ‘tree’ was not declared in this scope
         tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
         ^~~~
prog.cpp: In function ‘void solve()’:
prog.cpp:159:5: error: ‘cin’ was not declared in this scope
     cin >> n;
     ^~~
prog.cpp:160:5: error: ‘vector’ was not declared in this scope
     vector<ll> a(n + 1);
     ^~~~~~
prog.cpp:160:12: error: ‘ll’ was not declared in this scope
     vector<ll> a(n + 1);
            ^~
prog.cpp:160:16: error: ‘a’ was not declared in this scope
     vector<ll> a(n + 1);
                ^
prog.cpp:163:24: error: ‘vals’ was not declared in this scope
     vector<vector<ll>> vals(6);
                        ^~~~
prog.cpp:168:50: error: ‘sq_f’ was not declared in this scope
         for (int s = 1; s < 6; s++) vals[s][i] = sq_f(vals[s - 1][i]);
                                                  ^~~~
prog.cpp:191:13: error: ‘cout’ was not declared in this scope
             cout << st.query(l, r) << endl;
             ^~~~
prog.cpp:191:24: error: ‘struct Lazy_Segment_Tree’ has no member named ‘query’
             cout << st.query(l, r) << endl;
                        ^~~~~
prog.cpp:191:39: error: ‘endl’ was not declared in this scope
             cout << st.query(l, r) << endl;
                                       ^~~~
prog.cpp:191:39: note: suggested alternative: ‘enum’
             cout << st.query(l, r) << endl;
                                       ^~~~
                                       enum
stdout 
Standard output is empty
https://ideone.com/QxVmPK
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

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!