Submission #551328

#	Time	Username	Problem	Language	Result	Execution time	Memory
551328		Jarif_Rahman	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	285 ms	190924 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 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;
        }
    };

    node* v;
    int cnt = 0;

    int new_node(int l, int r){
        v[cnt] = node(0, l, r);
        return cnt++;
    }

    void pushdown(node &nd){
        if(nd.ln == -1)
            nd.ln = new_node(nd.l, (nd.l+nd.r)/2),
            nd.rn = new_node((nd.l+nd.r)/2+1, nd.r);

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

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

        nd.lazy_assign = -1;
    }

    sparse_segtree(int n){
        v = new node[maxn];
        int k = 1;
        while(k < n) k*=2;
        new_node(0, k-1);
    }

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

    ll sum(node &nd, int l, int r){
        if(nd.l > r || nd.r < l) return 0;
        if(nd.l >= l && nd.r <= r) return nd.sm;
        pushdown(nd);
        ll rt = sum(v[nd.ln], l, r) + sum(v[nd.rn], l, r);
        nd.sm = v[nd.ln].sm+v[nd.rn].sm;
        return rt;
    }
    ll sum(int l, int r){
        return sum(v[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: 100 / 100