Submission #551328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551328	2022-04-20T10:13:21 Z	Jarif_Rahman	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	285 ms	190924 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 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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	188108 KB	Output is correct
2	Correct	75 ms	188108 KB	Output is correct
3	Correct	74 ms	188164 KB	Output is correct
4	Correct	84 ms	188236 KB	Output is correct
5	Correct	86 ms	188372 KB	Output is correct
6	Correct	87 ms	188364 KB	Output is correct
7	Correct	86 ms	188296 KB	Output is correct
8	Correct	152 ms	189132 KB	Output is correct
9	Correct	243 ms	190240 KB	Output is correct
10	Correct	244 ms	190264 KB	Output is correct
11	Correct	250 ms	190252 KB	Output is correct
12	Correct	245 ms	190380 KB	Output is correct
13	Correct	230 ms	190640 KB	Output is correct
14	Correct	225 ms	190924 KB	Output is correct
15	Correct	284 ms	190800 KB	Output is correct
16	Correct	284 ms	190848 KB	Output is correct
17	Correct	226 ms	190768 KB	Output is correct
18	Correct	234 ms	190784 KB	Output is correct
19	Correct	285 ms	190924 KB	Output is correct
20	Correct	285 ms	190860 KB	Output is correct