Submission #1266484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266484		hyakup	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	320 KiB

apple

// https://oj.uz/problem/view/IZhO12_apple
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int inf = 1e9 + 10;

class LazyDynamicSegtree{
private:
  ll min_id, max_id;

  struct Node{
    int val, lazy, l, r;
    Node() : val(0), l(0), r(0), lazy(0) {}
  };
  vector<Node> seg;

  int create(){
    seg.emplace_back();
    return seg.size() - 1;
  }

  int l( int pos ){
    if( seg[pos].l == 0 ){ int aux = create(); seg[pos].l = aux; }
    return seg[pos].l;
  }

  int r( int pos ){
    if( seg[pos].r == 0 ){ int aux = create(); seg[pos].r = aux; }
    return seg[pos].r;
  }

  void refresh( int pos, ll ini, ll fim ){
    if( seg[pos].lazy == 0 ) return;
    int x = seg[pos].lazy; seg[pos].lazy = 0;
    seg[pos].val = 1LL*x*(fim - ini + 1);

    if( ini == fim ) return;
    l(pos); r(pos);
    seg[l(pos)].lazy = x;
    seg[r(pos)].lazy = x;
  }

  void update( int pos, ll ini, ll fim, ll ki, ll kf, int val ){
    refresh( pos, ini, fim );
    if( ki > fim || ini > kf ) return;
    if( ki <= ini && fim <= kf ){
      seg[pos].lazy = val;
      refresh( pos, ini, fim );
      return;
    }
    ll mid = (ini + fim)>>1;
    update( l(pos), ini, mid, ki, kf, val ); update( r(pos), mid + 1, fim, ki, kf, val );
    seg[pos].val = seg[seg[pos].l].val + seg[seg[pos].r].val;
  }

  int query( int pos, ll ini, ll fim, ll ki, ll kf ){
    refresh( pos, ini, fim );
    if( ki > fim || ini > kf ) return 0;
    if( ki <= ini && fim <= kf ) return seg[pos].val;
    ll mid = (ini + fim)>>1;
    return query( l(pos), ini, mid, ki, kf ) + query( r(pos), mid + 1, fim, ki, kf );
  }
public:
  LazyDynamicSegtree( ll min_id, ll max_id ){ create(); create(); }

  void update( ll l, ll r, int val ){ update( 1, min_id, max_id, l, r, val ); }
  int query( ll l, ll r ){ return query( 1, min_id, max_id, l, r ); }
};

int main(){
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int q; cin >> q;

  LazyDynamicSegtree seg( 0, inf );

  int c = 0;
  while( q-- ){
    int t, l, r; cin >> t >> l >> r;
    l += c; r += c;
    if( t == 1 ){
      c = seg.query( l, r );
      cout << c << endl;
    }
    else seg.update( l, r, 1 );
  }
}

• Subtask 1: 0 / 100