답안 #348564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348564 2021-01-15T08:29:50 Z nicolaalexandra 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
857 ms 232796 KB
#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    int sum,lazy;
    segment_tree *left, *right;
    segment_tree (){
        left = right = NULL;
        sum = lazy = 0;
    }
};

segment_tree *rad;
int q,tip,x,y,sol,n,c;


void update_lazy (segment_tree *nod, int st, int dr){
    if (nod == NULL || !nod->lazy)
        return;

    if (st != dr){

        if (nod->left == NULL)
            nod->left = new segment_tree();
        if (nod->right == NULL)
            nod->right = new segment_tree();

        int mid = (st+dr)>>1;
        nod->left->sum = mid-st+1;
        nod->left->lazy = 1;

        nod->right->sum = dr-mid;
        nod->right->lazy = 1;
    }
    nod->lazy = 0;
}

void update (segment_tree *nod, int st, int dr, int x, int y){

    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){

        nod->sum = dr - st + 1;
        nod->lazy = 1;
        update_lazy (nod,st,dr);

        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid){
        if (nod->left == NULL)
            nod->left = new segment_tree();
        update (nod->left,st,mid,x,y);
    }

    if (y > mid){
        if (nod->right == NULL)
            nod->right = new segment_tree();
        update (nod->right,mid+1,dr,x,y);
    }

    nod->sum = 0;
    if (nod->left != NULL){
        update_lazy (nod->left,st,mid);
        nod->sum += nod->left->sum;
    }

    if (nod->right != NULL){
        update_lazy (nod->right,mid+1,dr);
        nod->sum += nod->right->sum;
    }

    //nod->sum = nod->left->sum + nod->right->sum;

}

void query (segment_tree *nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        sol += nod->sum;
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid){
        //if (nod->left == NULL)
          //  nod->left = new segment_tree();
        if (nod->left != NULL)
            query (nod->left,st,mid,x,y);
    }
    if (y > mid){
        //if (nod->right == NULL)
          //  nod->right = new segment_tree();
        if (nod->right != NULL)
            query (nod->right,mid+1,dr,x,y);
    }

}



int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    rad = new segment_tree();
    n = 1000000000;

    cin>>q;
    c = 0;
    for (;q--;){
        cin>>tip>>x>>y;
        x += c, y += c;
        if (tip == 1){
            sol = 0;
            query (rad,1,n,x,y);
            cout<<sol<<"\n";

            c = sol;

        } else update (rad,1,n,x,y);
    }


    return 0;
}
# 결과 실행 시간 메모리 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 5356 KB Output is correct
5 Correct 41 ms 6508 KB Output is correct
6 Correct 40 ms 6252 KB Output is correct
7 Correct 40 ms 6508 KB Output is correct
8 Correct 279 ms 47340 KB Output is correct
9 Correct 565 ms 81004 KB Output is correct
10 Correct 580 ms 90476 KB Output is correct
11 Correct 611 ms 97772 KB Output is correct
12 Correct 607 ms 101100 KB Output is correct
13 Correct 579 ms 123244 KB Output is correct
14 Correct 575 ms 124780 KB Output is correct
15 Correct 838 ms 226028 KB Output is correct
16 Correct 838 ms 227436 KB Output is correct
17 Correct 590 ms 129132 KB Output is correct
18 Correct 588 ms 129132 KB Output is correct
19 Correct 857 ms 232684 KB Output is correct
20 Correct 853 ms 232796 KB Output is correct