Submission #427136

#	Time	Username	Problem	Language	Result	Execution time	Memory
427136		MilosMilutinovic	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	499 ms	132932 KiB

apple

#include <bits/stdc++.h>
using namespace std;

const int N=600050;
const int M=20*N;

int ls[M],rs[M],st[M],lzy[M],root,tsz;

void push(int c,int ss,int se){
    if(lzy[c]){
        st[c]=max(0,se-ss+1);
        if(ss!=se&&!ls[c])ls[c]=++tsz;
        if(ss!=se&&!rs[c])rs[c]=++tsz;
        if(ss!=se)lzy[ls[c]]=1;
        if(ss!=se)lzy[rs[c]]=1;
        lzy[c]=0;
    }
}

void Set(int&c,int ss,int se,int qs,int qe){
    if(!c)c=++tsz;
    push(c,ss,se);
    if(ss>se||ss>qe||se<qs)return;
    if(qs<=ss&&se<=qe){
        lzy[c]=1;
        push(c,ss,se);
        return;
    }
    int mid=ss+se>>1;
    Set(ls[c],ss,mid,qs,qe);
    Set(rs[c],mid+1,se,qs,qe);
    st[c]=st[ls[c]]+st[rs[c]];
}

int Get(int&c,int ss,int se,int qs,int qe){
    if(!c)c=++tsz;
    push(c,ss,se);
    if(ss>se||ss>qe||se<qs)return 0;
    if(qs<=ss&&se<=qe)return st[c];
    int mid=ss+se>>1;
    int L=Get(ls[c],ss,mid,qs,qe);
    int R=Get(rs[c],mid+1,se,qs,qe);
    return L+R;
}

int main(){
    int q;scanf("%i",&q);
    int lst=0;
    while(q--){
        int type,x,y;scanf("%i%i%i",&type,&x,&y);
        x=x+lst;
        y=y+lst;
        if(type==2)Set(root,1,1e9,x,y);
        else{
            lst=Get(root,1,1e9,x,y);
            printf("%i\n",lst);
        }
    }
    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'void Set(int&, int, int, int, int)':
apple.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=ss+se>>1;
      |             ~~^~~
apple.cpp: In function 'int Get(int&, int, int, int, int)':
apple.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid=ss+se>>1;
      |             ~~^~~
apple.cpp: In function 'int main()':
apple.cpp:47:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
apple.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         int type,x,y;scanf("%i%i%i",&type,&x,&y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100