Submission #427136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427136	2021-06-14T12:39:19 Z	MilosMilutinovic	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	499 ms	132932 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	20 ms	3036 KB	Output is correct
5	Correct	18 ms	3620 KB	Output is correct
6	Correct	18 ms	3548 KB	Output is correct
7	Correct	18 ms	3656 KB	Output is correct
8	Correct	146 ms	26008 KB	Output is correct
9	Correct	318 ms	44040 KB	Output is correct
10	Correct	412 ms	49352 KB	Output is correct
11	Correct	353 ms	53520 KB	Output is correct
12	Correct	337 ms	55404 KB	Output is correct
13	Correct	280 ms	68876 KB	Output is correct
14	Correct	294 ms	69504 KB	Output is correct
15	Correct	447 ms	126548 KB	Output is correct
16	Correct	482 ms	129664 KB	Output is correct
17	Correct	332 ms	74132 KB	Output is correct
18	Correct	307 ms	74172 KB	Output is correct
19	Correct	481 ms	132720 KB	Output is correct
20	Correct	499 ms	132932 KB	Output is correct