Submission #551641

#	Time	Username	Problem	Language	Result	Execution time	Memory
551641		Jarif_Rahman	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	466 ms	262144 KiB

apple

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

template<int maxn>
struct sparse_segtree{
    struct node{
        int id;
        int l, r;
        int ln = -1, rn = -1;
        ll sm, lazy_assign = -1;
        node(){
            sm = 0;
        }
        node(ll x, int _l, int _r){
            l = _l, r = _r;
            sm = x;
        }
    };

    vector<node> v;
    int cnt = 0;

    int new_node(int l, int r){
        v.pb(node(0, l, r));
        v.back().id = cnt;
        return cnt++;
    }

    void pushdown(int nd){
        if(v[nd].ln == -1 && v[nd].rn == -1){
            v[nd].ln = new_node(v[nd].l, (v[nd].l+v[nd].r)/2);
            v[nd].rn = new_node((v[nd].l+v[nd].r)/2+1, v[nd].r);
        }

        if(v[nd].lazy_assign == -1) return;

        int ln = v[nd].ln, rn = v[nd].rn;
        
        v[ln].sm = v[nd].lazy_assign*(v[ln].r-v[ln].l+1);
        v[ln].lazy_assign = v[nd].lazy_assign;

        v[rn].sm = v[nd].lazy_assign*(v[rn].r-v[rn].l+1);
        v[rn].lazy_assign = v[nd].lazy_assign;

        v[nd].lazy_assign = -1;
    }

    sparse_segtree(int n){
        int k = 1;
        while(k < n) k*=2;
        new_node(0, k-1);
    }

    void assign(int nd, int l, int r, ll x){
        if(v[nd].l > r || v[nd].r < l) return;
        if(v[nd].l >= l && v[nd].r <= r){
            v[nd].lazy_assign = x;
            v[nd].sm = x*(v[nd].r-v[nd].l+1);
            return;
        }
        pushdown(nd);
        assign(v[nd].ln, l, r, x);
        assign(v[nd].rn, l, r, x);
        v[nd].sm = v[v[nd].ln].sm+v[v[nd].rn].sm;
    }
    void assign(int l, int r, ll x){
        assign(0, l, r, x);
    }

    ll sum(int nd, int l, int r){
        if(v[nd].l > r || v[nd].r < l) return 0;
        if(v[nd].l >= l && v[nd].r <= r) return v[nd].sm;
        pushdown(nd);
        ll rt = sum(v[nd].ln, l, r) + sum(v[nd].rn, l, r);
        v[nd].sm = v[v[nd].ln].sm+v[v[nd].rn].sm;
        return rt;
    }
    ll sum(int l, int r){
        return sum(0, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    sparse_segtree<int(60e5)> sp(1e9);

    int c = 0;
    int q; cin >> q;
    while(q--){
        int tt, x, y; cin >> tt >> x >> y;
        x--, y--;
        if(tt == 1){
            c = sp.sum(x+c, y+c);
            cout << c << "\n";
        }
        else{
            sp.assign(x+c, y+c, 1);
        }
    }
}

• Subtask 1: 0 / 100