답안 #339138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339138 2020-12-24T16:23:37 Z beksultan04 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
769 ms 205676 KB
#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(){
      |      ^
# 결과 실행 시간 메모리 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