Submission #339130

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339130	2020-12-24T16:20:32 Z	beksultan04	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	865 ms	259820 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);
}

void update(node *root, int &ql, int &qr){
    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,ql,qr);
    update(root->bala2,ql,qr);
    root-> sum = root->bala1->sum + root->bala2->sum;
}

int get_ans(node *root,int &ql,int &qr){
    if (ql > root->r || qr < root->l)ret 0;

    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);
    if (qr >= root->r && root->l >= ql)ret root->sum;
    ret get_ans(root->bala1,ql,qr) + get_ans(root->bala2,ql,qr);
}


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

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

        }
    }
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	33 ms	6124 KB	Output is correct
5	Correct	41 ms	7404 KB	Output is correct
6	Correct	41 ms	7148 KB	Output is correct
7	Correct	42 ms	7404 KB	Output is correct
8	Correct	285 ms	55532 KB	Output is correct
9	Correct	601 ms	95852 KB	Output is correct
10	Correct	598 ms	106092 KB	Output is correct
11	Correct	606 ms	113772 KB	Output is correct
12	Correct	627 ms	117292 KB	Output is correct
13	Correct	614 ms	135932 KB	Output is correct
14	Correct	607 ms	136812 KB	Output is correct
15	Correct	865 ms	252012 KB	Output is correct
16	Correct	857 ms	254084 KB	Output is correct
17	Correct	633 ms	142484 KB	Output is correct
18	Correct	644 ms	142724 KB	Output is correct
19	Correct	840 ms	259692 KB	Output is correct
20	Correct	825 ms	259820 KB	Output is correct