Submission #479319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479319	2021-10-11T08:53:19 Z	jhhope1	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	344 ms	134532 KB

apple

#include<bits/stdc++.h>
using namespace std;
int C, M;
const int MAXN = 1e9;
struct Node{
    int val, lazy_set, l, r;
    Node(int val, int lazy_set):val(val),lazy_set(lazy_set),l(-1),r(-1){};
};
struct Seg{
    vector<Node> V;
    Seg(){
        V.emplace_back(0, 0);
    }
    void push_down(int s, int e, int v){
        int m = (s+e)>>1;
        if(V[v].lazy_set){
            if(V[v].l == -1){
                V[v].l = V.size();
                V.emplace_back(V[v].lazy_set*(m-s+1), V[v].lazy_set);
            }
            else{
                V[V[v].l].val = V[v].lazy_set * (m-s+1);
                V[V[v].l].lazy_set = V[v].lazy_set;
            }
            if(V[v].r == -1){
                V[v].r = V.size();
                V.emplace_back(V[v].lazy_set * (e-m), V[v].lazy_set);
            }else{
                V[V[v].r].val = V[v].lazy_set * (e-m);
                V[V[v].r].lazy_set = V[v].lazy_set;
            }
            V[v].lazy_set = 0;
        }
        else{
            if(V[v].l == -1){
                V[v].l = V.size();
                V.emplace_back(0, 0);
            }
            if(V[v].r == -1){
                V[v].r = V.size();
                V.emplace_back(0, 0);
            }
        }
    }
    void update(int s, int e, int l, int r, int v, int val){
        if(e<l || r<s){
            return;
        }
        if(l<=s && e<=r){
            V[v].val = val * (e-s+1);
            V[v].lazy_set = val;
            return;
        }
        push_down(s, e, v);
        int m = (s+e)>>1;
        update(s, m, l, r, V[v].l, val);
        update(m+1, e, l, r, V[v].r, val);
        V[v].val = V[V[v].l].val + V[V[v].r].val;
    }
    int sum(int s, int e, int l, int r, int v){
        if(e<l || r<s){
            return 0;
        }
        if(l<=s && e<=r){
            return V[v].val;
        }
        push_down(s, e, v);
        int m = (s+e)>>1;
        return sum(s, m, l, r, V[v].l) + sum(m+1, e, l, r, V[v].r);
    }
}S;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>M;
    for(int i=0,t,x,y ; i<M ; i++){
        cin>>t;
        if(t==1){
            cin>>x>>y;
            C = S.sum(1, MAXN, x+C, y+C, 0);
            cout<<C<<"\n";
        }
        else if(t==2){
            cin>>x>>y;
            S.update(1, MAXN, x+C, y+C, 0, 1);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	13 ms	2632 KB	Output is correct
5	Correct	14 ms	2632 KB	Output is correct
6	Correct	13 ms	2632 KB	Output is correct
7	Correct	20 ms	2632 KB	Output is correct
8	Correct	113 ms	17572 KB	Output is correct
9	Correct	216 ms	34572 KB	Output is correct
10	Correct	210 ms	34448 KB	Output is correct
11	Correct	213 ms	34380 KB	Output is correct
12	Correct	224 ms	34376 KB	Output is correct
13	Correct	218 ms	68552 KB	Output is correct
14	Correct	236 ms	68560 KB	Output is correct
15	Correct	344 ms	134360 KB	Output is correct
16	Correct	327 ms	134532 KB	Output is correct
17	Correct	210 ms	68524 KB	Output is correct
18	Correct	220 ms	68516 KB	Output is correct
19	Correct	311 ms	134312 KB	Output is correct
20	Correct	315 ms	134372 KB	Output is correct