Submission #427132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
427132	2021-06-14T12:38:30 Z	MilosMilutinovic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	428 ms	129868 KB

apple

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

const int N=200050;
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

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	204 KB	Output is correct
4	Correct	15 ms	3020 KB	Output is correct
5	Correct	22 ms	3700 KB	Output is correct
6	Correct	18 ms	3520 KB	Output is correct
7	Correct	18 ms	3784 KB	Output is correct
8	Correct	151 ms	25928 KB	Output is correct
9	Correct	341 ms	45796 KB	Output is correct
10	Correct	343 ms	51104 KB	Output is correct
11	Correct	428 ms	55264 KB	Output is correct
12	Correct	355 ms	57152 KB	Output is correct
13	Runtime error	340 ms	129868 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-