제출 #1254097

#제출 시각아이디문제언어결과실행 시간메모리
1254097kbity원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
253 ms132316 KiB
// 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[v].l == -1 ? 0 : data[data[v].l].val,
      data[v].r == -1 ? 0 : 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;

    // no matter how far we go into the subtree, the result will always be zero
    if (data[v].val == 0)
      return 0;

    // the entire subtree is coloured, we can calculate the result right now
    if (data[v].val == y-x+1) {
      if (x<a && y>b)
        return b-a+1;
      else
        return (x<a ? y-a+1 : b-x+1);
    }

    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...