Submission #1077315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077315		vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	33 ms	3164 KiB

apple

#include<bits/stdc++.h>
using namespace std;
#define N 1<<23
int sz[N],cnt[N],ch[N][2],CC,RT;
int newnode(int s){
    return sz[++CC]=s,CC;
}
void setripe(int &i,int l,int r,int ll,int rr){
    if(!i) i=newnode(r-l+1);
    if(ll>r||l>rr) return;
    if(cnt[i]==sz[i])return;
    if(ll<=l&&r<=rr)
        return void(cnt[i]=sz[i]);
    setripe(ch[i][0],l,l+r>>1,ll,rr);
    setripe(ch[i][1],l+r+2>>1,r,ll,rr);
    cnt[i]=cnt[ch[i][0]]+cnt[ch[i][1]];
}
int qry(int i,int l,int r,int ll,int rr){
    if(!i) return 0;
    if(ll>r||l>rr) return 0;
    if(ll<=l&&r<=rr) return cnt[i];
    if(cnt[i]==sz[i]) return(min(r,rr)-max(l,ll)+1);
    return qry(ch[i][0],l,l+r>>1,ll,rr)+
        qry(ch[i][1],l+r+2>>1,r,ll,rr);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int q,la=0;
    cin>>q;
    while(q--){
        int a,b,c;
        cin>>a>>b>>c;
        b+=la,c+=la;
        if(a==2)
            setripe(RT,1,1e9,b,c);
        else cout<<(la=qry(RT,1,1e9,b,c))<<'\n';
    }
}

Compilation message (stderr)

apple.cpp: In function 'void setripe(int&, int, int, int, int)':
apple.cpp:14:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     setripe(ch[i][0],l,l+r>>1,ll,rr);
      |                        ~^~
apple.cpp:15:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     setripe(ch[i][1],l+r+2>>1,r,ll,rr);
      |                      ~~~^~
apple.cpp: In function 'int qry(int, int, int, int, int)':
apple.cpp:23:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     return qry(ch[i][0],l,l+r>>1,ll,rr)+
      |                           ~^~
apple.cpp:24:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         qry(ch[i][1],l+r+2>>1,r,ll,rr);
      |                      ~~~^~

• Subtask 1: 100 / 100