Submission #551320

#	Time	Username	Problem	Language	Result	Execution time	Memory
551320		Jarif_Rahman	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	92 ms	235148 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;
        node *ln, *rn;
        ll sm, lazy_assign;
        node(){
            sm = 0, lazy_assign = -1, ln = nullptr, rn = nullptr;
        }
        node(ll x, int _l, int _r){
            l = _l, r = _r;
            ln = nullptr, rn = nullptr;
            sm = x, lazy_assign = -1;
        }
        void pushdown(){
            if(lazy_assign == -1) return;
            ln->sm = lazy_assign*(r-l+1)/2;
            ln->lazy_assign = lazy_assign;
            rn->sm = lazy_assign*(r-l+1)/2;
            rn->lazy_assign = lazy_assign;
            lazy_assign = -1;
        }
        void getsum(){
            sm = ln->sm + rn->sm;
        }
    };

    node* v;
    int cnt = 0;

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

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

    void assign(int l, int r, node *nd, 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;
        }
        int md = (nd->l+nd->r)/2;
        if(!nd->ln) nd->ln = new_node(nd->l, md);
        if(!nd->rn) nd->rn = new_node(md+1, nd->r);
        nd->pushdown();
        assign(l, r, nd->ln, x);
        assign(l, r, nd->rn, x);
        nd->getsum();
    }
    void assign(int l, int r, ll x){
        assign(l, r, &v[0], x);
    }

    ll sum(int l, int r, node *nd){
        if(nd->l > r || nd->r < l) return 0;
        if(nd->l >= l && nd->r <= r) return nd->sm;
        int md = (nd->l+nd->r)/2;
        if(!nd->ln) nd->ln = new_node(nd->l, md);
        if(!nd->rn) nd->rn = new_node(md+1, nd->r);
        nd->pushdown();
        ll rt = sum(l, r, nd->ln) + sum(l, r, nd->rn);
        nd->getsum();
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, &v[0]);
    }
};

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){
            ll ans = sp.sum(x+c, y+c);
            c+=ans;
            cout << ans << "\n";
        }
        else{
            sp.assign(x+c, y+c, 1);
        }
    }
}

• Subtask 1: 0 / 100