답안 #1008945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008945	2024-06-27T06:43:08 Z	krit3379	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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