Submission #479321

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479321	2021-10-11T08:55:33 Z	jhhope1	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	313 ms	132392 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){};
    Node():val(0),lazy_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();
        }
        if(V[v].r == -1){
            V[v].r = V.size();
            V.emplace_back();
        }
        if(V[v].lazy_set){
            V[V[v].l].val = V[v].lazy_set * (m-s+1);
            V[V[v].l].lazy_set = V[v].lazy_set;
            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;
        }
    }
    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	11 ms	2504 KB	Output is correct
5	Correct	13 ms	2504 KB	Output is correct
6	Correct	13 ms	2504 KB	Output is correct
7	Correct	15 ms	2504 KB	Output is correct
8	Correct	93 ms	16932 KB	Output is correct
9	Correct	201 ms	33432 KB	Output is correct
10	Correct	205 ms	33424 KB	Output is correct
11	Correct	203 ms	33372 KB	Output is correct
12	Correct	211 ms	33460 KB	Output is correct
13	Correct	201 ms	66512 KB	Output is correct
14	Correct	212 ms	66536 KB	Output is correct
15	Correct	313 ms	132264 KB	Output is correct
16	Correct	302 ms	132136 KB	Output is correct
17	Correct	210 ms	66540 KB	Output is correct
18	Correct	228 ms	66440 KB	Output is correct
19	Correct	303 ms	132264 KB	Output is correct
20	Correct	299 ms	132392 KB	Output is correct