Submission #479325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479325	2021-10-11T09:06:36 Z	jhhope1	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	340 ms	132264 KB

apple

#include<bits/stdc++.h>
using namespace std;
int C, M;
const int MAXN = 1e9;
struct Node{
    int val, set, l, r;
    Node(int val, int set):val(val),set(set),l(-1),r(-1){};
    Node():val(0),set(0),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].l == -1){
            V[v].l = V.size();
            V.emplace_back();
            V[v].r = V.size();
            V.emplace_back();
        }
        if(V[v].set){
            V[V[v].l].val = V[v].set * (m-s+1);
            V[V[v].r].val = V[v].set * (e-m);
            V[V[v].l].set = V[V[v].r].set = V[v].set;
            V[v].set = 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].set = val;
            return;
        }
        int m = (s+e)>>1;
        push_down(s, e, v);
        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	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	10 ms	2504 KB	Output is correct
5	Correct	12 ms	2504 KB	Output is correct
6	Correct	14 ms	2544 KB	Output is correct
7	Correct	12 ms	2504 KB	Output is correct
8	Correct	95 ms	16972 KB	Output is correct
9	Correct	200 ms	33396 KB	Output is correct
10	Correct	190 ms	33384 KB	Output is correct
11	Correct	199 ms	33456 KB	Output is correct
12	Correct	193 ms	33344 KB	Output is correct
13	Correct	200 ms	66556 KB	Output is correct
14	Correct	193 ms	66536 KB	Output is correct
15	Correct	317 ms	132136 KB	Output is correct
16	Correct	340 ms	132208 KB	Output is correct
17	Correct	202 ms	66492 KB	Output is correct
18	Correct	243 ms	66476 KB	Output is correct
19	Correct	298 ms	132264 KB	Output is correct
20	Correct	295 ms	132216 KB	Output is correct