Submission #848600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848600	2023-09-13T02:23:56 Z	Darren0724	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	245 ms	81328 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(5000000,{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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	78684 KB	Output is correct
2	Correct	10 ms	78684 KB	Output is correct
3	Correct	11 ms	78520 KB	Output is correct
4	Correct	24 ms	78684 KB	Output is correct
5	Correct	27 ms	78824 KB	Output is correct
6	Correct	26 ms	78896 KB	Output is correct
7	Correct	27 ms	78680 KB	Output is correct
8	Correct	103 ms	79636 KB	Output is correct
9	Correct	196 ms	80668 KB	Output is correct
10	Correct	219 ms	80824 KB	Output is correct
11	Correct	211 ms	81032 KB	Output is correct
12	Correct	207 ms	80668 KB	Output is correct
13	Correct	202 ms	81236 KB	Output is correct
14	Correct	211 ms	81056 KB	Output is correct
15	Correct	227 ms	81236 KB	Output is correct
16	Correct	230 ms	81236 KB	Output is correct
17	Correct	205 ms	81180 KB	Output is correct
18	Correct	211 ms	81044 KB	Output is correct
19	Correct	245 ms	81328 KB	Output is correct
20	Correct	228 ms	81316 KB	Output is correct