Submission #1253707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253707		kbity	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	407 ms	263536 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<<')';}
int merge(int l, int r) {
  return l+r;
}

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

  void init(int sz) {
    base = 1 << (int)ceil(log2l(sz));
    data.clear();
    data.push_back(node());
  }

  int makenode(int parent) {
    data.push_back(node());
    // TODO: check if this is valid
    // NOTE: probably not, fuck it
    // data.back().val = parent.val;
    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(v);
      if (data[v].r == -1) data[v].r = makenode(v);

      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(v);
    if (b>=mid+1 && data[v].r == -1)
      data[v].r = makenode(v);

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

    data[v].val = merge(
      data[v].l == -1 ? 0 : data[data[v].l].val,
      data[v].r == -1 ? 0 : data[data[v].r].val
    );
  }
  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(
      data[v].l == -1 ? 0 : query(a,b,data[v].l,x,mid),
      data[v].r == -1 ? 0 : query(a,b,data[v].r,mid+1,y)
    );
  }
  int query(int l, int r) {
    return query(l,r,0,0,base-1);
  }
};

// NOTE: forced online
int dec_C = 0;
tuple<int,int,int> decode_query() {
  int T, x, y;
  cin >> T >> x >> y;
  #ifdef NODECODE
  return {T,x,y};
  #else
  return {T,x+dec_C,y+dec_C};
  #endif
}

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

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

    sparseSegment tree;
    tree.init(1e9+7);

    int t,x,y;

    while(M--) {
      tie(t,x,y) = decode_query();

      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