Submission #551641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551641	2022-04-21T08:54:01 Z	Jarif_Rahman	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	466 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	5572 KB	Output is correct
5	Correct	17 ms	5604 KB	Output is correct
6	Correct	18 ms	5600 KB	Output is correct
7	Correct	20 ms	5592 KB	Output is correct
8	Correct	125 ms	41576 KB	Output is correct
9	Correct	262 ms	82632 KB	Output is correct
10	Correct	272 ms	82720 KB	Output is correct
11	Correct	274 ms	82624 KB	Output is correct
12	Correct	286 ms	82664 KB	Output is correct
13	Correct	288 ms	164992 KB	Output is correct
14	Correct	284 ms	165064 KB	Output is correct
15	Correct	413 ms	164832 KB	Output is correct
16	Correct	420 ms	164716 KB	Output is correct
17	Correct	300 ms	165116 KB	Output is correct
18	Correct	311 ms	165016 KB	Output is correct
19	Runtime error	466 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-