Submission #1286496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286496		ahmedisti73	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	361 ms	137216 KiB

apple

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifndef DeBuG
  #define dbg(...)
#endif
#define F first
#define S second
#define endl '\n'
#define PB push_back
using ll = long long;
using ld = long double;
using prr = pair<int,int>;
constexpr ll MAX = (1LL<<60) - 1;
inline void ha(){ cout<<"YES\n"; }
inline void na(){ cout<<"NO\n"; }
inline void na1(){ cout<<"-1\n"; }
inline string IS(ll x){ return to_string(x); }
inline ll SI(const string&s){ return stoll(s); }
// inline ll lcm(ll a,ll b) { if(!a||!b) return 0;
// ll g=gcd(a,b); __int128 res=(__int128)(a/g)*b; return res>(__int128)MAX?MAX:(ll)res;}
using orderS = tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long L, long long R) {return uniform_int_distribution<long long>(L, R)(rng);}

class SparseSegTree {

private:
    struct node {
        ll freq=0;
        ll lazy=0;
        int left=0;
        int right=0;
        bool lazy_flag=false;
    };
    vector<node> tree;
    const ll n;
    int timer=1;
    // int comb(int a,int b) { return a+b; }

    void apply(int cur,ll l,ll r,ll val) { // check here
        tree[cur].lazy=val;
        tree[cur].lazy_flag=true;
        tree[cur].freq=(r-l+1)*val;
    }

    void push_down(int cur,ll l,ll r){
        if(!tree[cur].left){
            tree[cur].left= ++timer;
            tree.PB(node());
        }
        if(!tree[cur].right){
            tree[cur].right= ++timer;
            tree.PB(node());
        }
        if(!tree[cur].lazy_flag) return;
        ll mid=(l+r)>>1;
        apply(tree[cur].left,l,mid,tree[cur].lazy);
        apply(tree[cur].right,mid+1,r,tree[cur].lazy);
        tree[cur].lazy_flag=false;
        tree[cur].lazy=0;
    }

    void upd(int cur,ll l,ll r,ll ql,ll qr,ll val) {
        if(qr<l || ql>r) return;
        if(ql<=l && r<=qr) apply(cur,l,r,val);
        else {
            push_down(cur,l,r);
            ll mid=(l+r)>>1;
            upd(tree[cur].left,l,mid,ql,qr,val);
            upd(tree[cur].right,mid+1,r,ql,qr,val);
            tree[cur].freq=
                tree[tree[cur].left].freq + tree[tree[cur].right].freq; // check here
        }
    }

    ll query(int cur,ll l,ll r,ll ql,ll qr) {
        if(qr<l || ql>r || !cur) return 0;
        if(ql<=l && r<=qr) return tree[cur].freq;
        push_down(cur,l,r);
        ll mid=(l+r)>>1;
        return query(tree[cur].left,l,mid,ql,qr) + 
               query(tree[cur].right,mid+1,r,ql,qr); // check here
    }

public:
    SparseSegTree(ll n,int q=0) : n(n) {
        if(q>0) { tree.reserve(2*q*__lg(n)); }
        tree.PB(node()); tree.PB(node());
    }
    void upd(ll ql,ll qr,ll val) { upd(1,1,n,ql,qr,val); }
    int query(ll ql,ll qr) {return query(1,1,n,ql,qr); }
};

void GLITCH_() {
    ll q; cin>>q;
    const ll range=1e9;
    SparseSegTree t(range+1,q);
    ll c=0;
    while(q--){
      ll type,l,r; cin>>type>>l>>r;
      if(type==1){
        c=t.query(l+c,r+c);
        cout<<c<<endl;
      }else{
        t.upd(l+c,r+c,1);
      }
    }
}
/*
4
2 2 3
1 1 3
2 2 3
1 -1 3
*/
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(10);
    auto _start=chrono::high_resolution_clock::now();
    int ttt=1;
    // cin>>ttt;
    for(int tt=1; tt<=ttt; tt++) {
        GLITCH_();

        #ifdef LOCAL
        auto _current_time = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(_current_time - _start).count();
        std::cerr << "        --C " << tt << " | T: " << elapsed << "s\n\n";
        #endif
    }
    cerr<<"⏱ "<<chrono::duration<double>(chrono::high_resolution_clock::now()-_start).count()<<"s\n";
    
    return 0;
}

• Subtask 1: 100 / 100