Submission #1253725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253725		kbity	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	383 ms	263680 KiB

apple

// https://oj.uz/problem/view/IZhO12_apple
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using LL=long long;
using LD=long double;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define ROF(i,l,r) for(auto i=(l);i>=(r);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ITF(e,c) for(auto&e:(c))
#define ssize(x) int(x.size())
#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second<<')';}
auto operator<<(auto&o,auto&x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct node {
  int l = -1, r = -1;
  bool lazy = 0;
  int val = 0;
};
auto&operator<<(auto&o, node n) {return o<<'('<<n.val<<(n.lazy ? "L" : "")<<"/"<<n.l<<", "<<n.r<<')';}
inline int merge(int l, int r) {
  return l+r;
}

struct sparseSegment {
  int base;
  vector<node> data;

  sparseSegment(int sz)
    :base(1 << (int)ceil(log2l(sz)))
  { (void)makenode(); /* create root node */ }

  inline int makenode() {
    data.push_back(node());
    return ssize(data)-1;
  }

  void propagate(int v, int l) {
    if (data[v].lazy == 0) return;
    data[v].val = l;
    if (l > 1) {
      if (data[v].l == -1) data[v].l = makenode();
      if (data[v].r == -1) data[v].r = makenode();

      data[data[v].l].lazy = 1;
      data[data[v].r].lazy = 1;
    }
    data[v].lazy = 0;
  }

  void update(int a, int b, int v, int x, int y) {
    if (v==-1) return;

    propagate(v, y-x+1);
    if (b<x||a>y) return;
    if (a<=x&&y<=b) {
      data[v].lazy = 1;
      propagate(v, y-x+1);
      return;
    }

    int mid = (x+y)/2;
    if (a<=mid && data[v].l == -1)
      data[v].l = makenode();
    if (b>=mid+1 && data[v].r == -1)
      data[v].r = makenode();

    update(a,b,data[v].l,x,mid);
    update(a,b,data[v].r,mid+1,y);

    data[v].val = merge(
      data[data[v].l].val,
      data[data[v].r].val
    );
  }
  inline void update(int l, int r) {
    update(l,r,0,0,base-1);
  }

  int query(int a, int b, int v, int x, int y) {
    if (v==-1) return 0;

    propagate(v, y-x+1);
    if (b<x||a>y) return 0;
    if (a<=x&&y<=b) return data[v].val;

    int mid = (x+y)/2;
    return merge(
      query(a,b,data[v].l,x,mid),
      query(a,b,data[v].r,mid+1,y)
    );
  }
  inline int query(int l, int r) {
    return query(l,r,0,0,base-1);
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  /// query handler
  {
    int M;
    cin >> M;

    sparseSegment tree(1e9+69);

    int t,x,y;
    int dec_C = 0;

    while(M--) {
      cin >> t >> x >> y;
      #ifndef NODECODE
      x+=dec_C, y+=dec_C;
      #endif

      if (t==1) {
        dec_C = tree.query(x,y);
        cout << dec_C << endl;
      } else {
        tree.update(x,y);
      }

      debug(tree.data);
    }   
  }

  return 0;
}

• Subtask 1: 0 / 100