Submission #848602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848602	2023-09-13T02:25:04 Z	Darren0724	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	203 ms	96076 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct segtree{
    struct seg{
        int lz,val,lc,rc;
    };
    vector<seg> v;
    int cnt1=0;
    int New(){
        return cnt1++;
    }
    segtree(){
        New();
        v.resize(3000000,{0,0,-1,-1});
    }
    int rv(seg &s,int l,int r){
        return (s.lz?r-l:s.val);
    }
    void check(seg &s){
        if(s.lc==-1){
            s.lc=New();
        }
        if(s.rc==-1){
            s.rc=New();
        }
    }
    void push(seg &s){
        v[s.lc].lz|=s.lz;
        v[s.rc].lz|=s.lz;
    }
    void pull(seg &s,int l,int m,int r){
        s.val=rv(v[s.lc],l,m)+rv(v[s.rc],m,r);
    }
    void add(seg &s,int a,int b,int l,int r){
        if(a<=l&&b>=r){
            s.lz=1;
            return;
        }
        check(s);
        push(s);
        int m=(l+r)>>1;
        if(a<m){
            add(v[s.lc],a,b,l,m);
        }
        if(b>m){
            add(v[s.rc],a,b,m,r);
        }
        pull(s,l,m,r);
    }
    int ask(seg &s,int a,int b,int l,int r){
        if(a<=l&&b>=r){
            return rv(s,l,r);
        }
        int m=(l+r)>>1;
        int ans=0;
        check(s);
        push(s);
        if(a<m){
            ans+=ask(v[s.lc],a,b,l,m);
        }
        if(b>m){
            ans+=ask(v[s.rc],a,b,m,r);
        }
        pull(s,l,m,r);
        return ans;
    }
};
int32_t main() {
    int n;cin>>n;
    segtree tr;
    int ans=0;
    const int p=1e9+1;
    for(int i=0;i<n;i++){
        int id;cin>>id;
        if(id==2){
            int a,b;cin>>a>>b;
            a+=ans,b+=ans;
            tr.add(tr.v[0],a,b+1,0,p);
        }
        else{
            int a,b;cin>>a>>b;
            a+=ans,b+=ans;
            ans=tr.ask(tr.v[0],a,b+1,0,p);
            cout<<ans<<endl;
        }
    }
    
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	47192 KB	Output is correct
2	Correct	6 ms	47192 KB	Output is correct
3	Correct	6 ms	47196 KB	Output is correct
4	Correct	20 ms	47196 KB	Output is correct
5	Correct	23 ms	47192 KB	Output is correct
6	Correct	26 ms	47196 KB	Output is correct
7	Correct	23 ms	47428 KB	Output is correct
8	Correct	96 ms	47440 KB	Output is correct
9	Correct	200 ms	47696 KB	Output is correct
10	Correct	192 ms	47696 KB	Output is correct
11	Correct	203 ms	47700 KB	Output is correct
12	Correct	199 ms	47624 KB	Output is correct
13	Correct	201 ms	47696 KB	Output is correct
14	Correct	202 ms	47700 KB	Output is correct
15	Runtime error	191 ms	96076 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-