Submission #548638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548638	2022-04-14T04:45:35 Z	krit3379	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	220 ms	58952 KB

apple

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

class node{
public:
    int sum;
    node *tl,*tr;
    node():tl(NULL),tr(NULL),sum(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&&!(l>rr||ll>mid))tl = new node();
        if(tl)tl->update(l,mid,ll,rr);
        if(!tr&&!(mid+1>rr||ll>r))tr = new node();
        if(tr)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 main(){
    int m,op,x,y,c=0;
    scanf("%d",&m);
    root = new node();
    while(m--){
        scanf("%d %d %d",&op,&x,&y);
        if(op==1){
            c=root->sol(1,1e9,x+c,y+c);
            printf("%d\n",c);
        }
        else root->update(1,1e9,x+c,y+c);
    }
    return 0;
}

Compilation message

apple.cpp: In constructor 'node::node()':
apple.cpp:8:15: warning: 'node::tr' will be initialized after [-Wreorder]
    8 |     node *tl,*tr;
      |               ^~
apple.cpp:7:9: warning:   'int node::sum' [-Wreorder]
    7 |     int sum;
      |         ^~~
apple.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     node():tl(NULL),tr(NULL),sum(0){}
      |     ^~~~
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",&m);
      |     ~~~~~^~~~~~~~~
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,&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	6 ms	1620 KB	Output is correct
5	Correct	9 ms	1876 KB	Output is correct
6	Correct	10 ms	1876 KB	Output is correct
7	Correct	9 ms	1900 KB	Output is correct
8	Correct	83 ms	13520 KB	Output is correct
9	Correct	108 ms	23928 KB	Output is correct
10	Correct	115 ms	26096 KB	Output is correct
11	Correct	128 ms	27712 KB	Output is correct
12	Correct	145 ms	28476 KB	Output is correct
13	Correct	105 ms	29644 KB	Output is correct
14	Correct	107 ms	30412 KB	Output is correct
15	Correct	220 ms	57572 KB	Output is correct
16	Correct	166 ms	57916 KB	Output is correct
17	Correct	124 ms	33488 KB	Output is correct
18	Correct	126 ms	33428 KB	Output is correct
19	Correct	166 ms	58952 KB	Output is correct
20	Correct	176 ms	58828 KB	Output is correct