Submission #339138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339138	2020-12-24T16:23:37 Z	beksultan04	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	769 ms	205676 KB

apple

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%lld",&a);
#define scan2(a,b) scanf("%lld %lld",&a, &b);
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
const int N = 1e5+12,INF=1e9+7;

struct node{
    int l, r,sum;
    bool pus;
    node *bala1, *bala2;
    node(int L, int R){
        bala1 = bala2 = NULL;
        sum=pus=0;
        l = L;
        r = R;
    }
};

void push(node *root){
    if (root->pus == 0)ret ;
    if (root->bala1 != NULL) root->bala1->pus |= root->pus;
    if (root->bala2 != NULL) root->bala2->pus |= root->pus;
    root->sum = (root->r - root->l + 1);
}

int ql,qr;
void update(node *root){
    push(root);

    if(root->l > qr || root->r < ql)return;
    if(root->l >= ql && root->r <= qr){
        root->pus = 1;
        push(root);
        return;
    }
    int mid = (root->l + root->r)>>1;
    if(root->bala1 == NULL)root->bala1 = new node(root->l,mid);
    if(root->bala2 == NULL)root->bala2 = new node(mid+1,root->r);
    push(root);
    update(root->bala1);
    update(root->bala2);
    root-> sum = root->bala1->sum + root->bala2->sum;
}
int get_ans(node *root){
    if (ql > root->r || qr < root->l)ret 0;

    push(root);
    if (qr >= root->r && root->l >= ql)ret root->sum;
    int mid = (root->l + root->r)>>1;
    if(root->bala1 == NULL)root->bala1 = new node(root->l,mid);
    if(root->bala2 == NULL)root->bala2 = new node(mid+1,root->r);
    push(root);
    ret get_ans(root->bala1) + get_ans(root->bala2);
}


main(){
    int m,ans=0;
    cin>>m;
    node *root = new node(1, 1e9+1);

    while (m--){
        char c;
        cin>>c>>ql>>qr;
        ql+=ans;
        qr+=ans;
        if (c == '2'){
            update(root);
        }
        else {
            ans = get_ans(root);
            cout <<ans<<"\n";

        }
    }
}

Compilation message

apple.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      |      ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	32 ms	4844 KB	Output is correct
5	Correct	40 ms	5996 KB	Output is correct
6	Correct	39 ms	5740 KB	Output is correct
7	Correct	40 ms	5868 KB	Output is correct
8	Correct	277 ms	43756 KB	Output is correct
9	Correct	553 ms	75628 KB	Output is correct
10	Correct	566 ms	83708 KB	Output is correct
11	Correct	574 ms	90092 KB	Output is correct
12	Correct	586 ms	93036 KB	Output is correct
13	Correct	549 ms	108140 KB	Output is correct
14	Correct	551 ms	109164 KB	Output is correct
15	Correct	752 ms	199532 KB	Output is correct
16	Correct	751 ms	201196 KB	Output is correct
17	Correct	570 ms	112748 KB	Output is correct
18	Correct	556 ms	112876 KB	Output is correct
19	Correct	763 ms	205628 KB	Output is correct
20	Correct	769 ms	205676 KB	Output is correct