Submission #1008945

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1008945	2024-06-27T06:43:08 Z	krit3379	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	133 ms	77140 KB

apple

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

class node{
public:
    int sum;
    node *tl,*tr;
    node():sum(0),tl(0),tr(0){}
    void upd(){
        sum=max(sum,(tl?tl->sum:0)+(tr?tr->sum:0));
    }
    void update(int l,int r,int ll,int rr){
        if(l>rr||ll>r)return ;
        if(ll<=l&&r<=rr){
            sum=r-l+1;
            return ;
        }
        int mid=(l+r)/2;
        if(!tl)tl=new node();
        if(!tr)tr=new node();
        tl->update(l,mid,ll,rr);
        tr->update(mid+1,r,ll,rr);
        upd();
    }
    int sol(int l,int r,int ll,int rr){
        if(l>rr||ll>r)return 0;
        if(ll<=l&&r<=rr)return sum;
        if(sum==r-l+1)return min(r,rr)-max(l,ll)+1;
        int mid=(l+r)/2;
        return (tl?tl->sol(l,mid,ll,rr):0)+(tr?tr->sol(mid+1,r,ll,rr):0);
    }
};
using pnode = node*;

pnode root;
int c;

int main(){
    int q,op,l,r;
    scanf("%d",&q);
    root = new node();
    while(q--){
        scanf("%d %d %d",&op,&l,&r);
        if(op==1){
            printf("%d\n",c=root->sol(1,1e9,l+c,r+c));
        }
        else{
            root->update(1,1e9,l+c,r+c);
        }
    }
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
apple.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d %d",&op,&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	5 ms	2140 KB	Output is correct
5	Correct	6 ms	2664 KB	Output is correct
6	Correct	7 ms	2652 KB	Output is correct
7	Correct	6 ms	2652 KB	Output is correct
8	Correct	40 ms	18512 KB	Output is correct
9	Correct	88 ms	33108 KB	Output is correct
10	Correct	96 ms	36180 KB	Output is correct
11	Correct	86 ms	38228 KB	Output is correct
12	Correct	84 ms	39252 KB	Output is correct
13	Correct	92 ms	41320 KB	Output is correct
14	Correct	86 ms	42320 KB	Output is correct
15	Correct	127 ms	75656 KB	Output is correct
16	Correct	133 ms	75812 KB	Output is correct
17	Correct	86 ms	43604 KB	Output is correct
18	Correct	87 ms	43624 KB	Output is correct
19	Correct	122 ms	77140 KB	Output is correct
20	Correct	126 ms	77136 KB	Output is correct