Submission #339135

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339135	2020-12-24T16:21:45 Z	beksultan04	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	779 ms	205804 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;

    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,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: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	33 ms	4844 KB	Output is correct
5	Correct	40 ms	5868 KB	Output is correct
6	Correct	40 ms	5740 KB	Output is correct
7	Correct	40 ms	5868 KB	Output is correct
8	Correct	301 ms	43756 KB	Output is correct
9	Correct	563 ms	75628 KB	Output is correct
10	Correct	583 ms	83708 KB	Output is correct
11	Correct	583 ms	89964 KB	Output is correct
12	Correct	599 ms	92908 KB	Output is correct
13	Correct	555 ms	108140 KB	Output is correct
14	Correct	554 ms	109036 KB	Output is correct
15	Correct	763 ms	199532 KB	Output is correct
16	Correct	767 ms	201324 KB	Output is correct
17	Correct	570 ms	112748 KB	Output is correct
18	Correct	566 ms	112876 KB	Output is correct
19	Correct	766 ms	205804 KB	Output is correct
20	Correct	779 ms	205676 KB	Output is correct