제출 #1253623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253623		kbity	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	26 ms	8932 KiB

apple

// https://oj.uz/problem/view/IZhO12_apple
// CASE: x+C, y+C <= 1e6 -> 35p
#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

int merge(int l, int r) {
  return l+r;
}
struct segment {
  int base;
  vector<int> data;
  vector<bool> lazy;

  void init(int sz) {
    base = 1 << (int)ceil(log2l(sz));
    data.resize(2*base, 0);
    lazy.resize(2*base, 0);
  }

  void propagate(int v, int l) {
    if (lazy[v] == 0) return;
    data[v] = l;
    if (v<base)
      lazy[2*v] = 1, lazy[2*v+1] = 1;
    lazy[v] = 0;
  }

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

    int mid = (x+y)/2;
    update(a,b,2*v,x,mid);
    update(a,b,2*v+1,mid+1,y);
    data[v] = merge(data[2*v], data[2*v+1]);
  }
  void update(int l, int r) {
    update(l,r,1,0,base-1);
  }

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

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

// NOTE: forced online
int dec_C = 0;
tuple<bool,int,int> decode_query() {
  int T, x, y;
  cin >> T >> x >> y;
  return {T-1,x+dec_C,y+dec_C};
}

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

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

    segment tree;
    tree.init(1<<20);

    bool t;
    int x,y;

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

  return 0;
}

• Subtask 1: 0 / 100