Submission #348564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348564	2021-01-15T08:29:50 Z	nicolaalexandra	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	857 ms	232796 KB

apple

#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;
}

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	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