Submission #580515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580515	2022-06-21T11:21:00 Z	LucaIlie	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	642 ms	232552 KB

apple

#include <bits/stdc++.h>

#define MIN_P 1
#define MAX_P 1000000000

using namespace std;

struct AINT {
    struct node {
        bool lazy;
        int sum;
        node *left, *right;
    };

    node *getNode() {
        node* nod = new node;

        nod->lazy = false;
        nod->sum = 0;
        nod->left = nod->right = NULL;

        return nod;
    }

    node *root = getNode();

    void update( node *nod, int l, int r, int lu, int ru ) {
        int mid = (l + r) / 2;

        if ( nod->lazy ) {
            nod->sum = r - l + 1;
            if ( l != r ) {
                if ( nod->left == NULL )
                    nod->left = getNode();
                if ( nod->right == NULL )
                    nod->right = getNode();
                nod->left->lazy = nod->right->lazy = true;
            }
            nod->lazy = false;
        }

        if ( l > ru || r < lu )
            return;
        if ( lu <= l && r <= ru ) {
            nod->sum = r - l + 1;
            if ( l != r ) {
                if ( nod->left == NULL )
                    nod->left = getNode();
                if ( nod->right == NULL )
                    nod->right = getNode();
                nod->left->lazy = nod->right->lazy = true;
            }
            nod->lazy = false;
            return;
        }
        if ( nod->left == NULL )
            nod->left = getNode();
        if ( nod->right == NULL )
            nod->right = getNode();
        update( nod->left, l, mid, lu, ru );
        update( nod->right, mid + 1, r, lu, ru );
        nod->sum = nod->left->sum + nod->right->sum;
    }
    void update( int l, int r ) {
        update( root, MIN_P, MAX_P, l, r );
    }

    int query( node *nod, int l, int r, int lq, int rq ) {
        int mid = (l + r) / 2;
        int sum;

        if ( nod->lazy ) {
            nod->sum = r - l + 1;
            if ( l != r ) {
                if ( nod->left == NULL )
                    nod->left = getNode();
                if ( nod->right == NULL )
                    nod->right = getNode();
                nod->left->lazy = nod->right->lazy = true;
            }
            nod->lazy = false;
        }

        if ( lq <= l && r <= rq ) {
            return nod->sum;
        }

        sum = 0;
        if ( mid >= lq ) {
            if ( nod->left == NULL )
                nod->left = getNode();
            sum += query( nod->left, l, mid, lq, rq );
        }
        if ( mid + 1 <= rq ) {
            if ( nod->right == NULL )
                nod->right = getNode();
            sum += query( nod->right, mid + 1, r, lq, rq );
        }
        //printf( "q: %d %d %d\n", l, r, sum );

        return sum;
    }
    int query( int l, int r ) {
        return query( root, MIN_P, MAX_P, l, r );
    }
};

AINT apples;

int main() {
    int m, t, l, r, a, c;

    c = 0;
    cin >> m;
    while ( m-- ) {
        cin >> t >> l >> r;
        l += c;
        r += c;

        if ( t == 1 ) {
            a = apples.query( l, r );
            cout << a << "\n";
            c = a;
        } else
            apples.update( l, r );
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	24 ms	5252 KB	Output is correct
5	Correct	28 ms	6400 KB	Output is correct
6	Correct	29 ms	6224 KB	Output is correct
7	Correct	30 ms	6408 KB	Output is correct
8	Correct	210 ms	47180 KB	Output is correct
9	Correct	409 ms	80856 KB	Output is correct
10	Correct	423 ms	90440 KB	Output is correct
11	Correct	468 ms	97596 KB	Output is correct
12	Correct	430 ms	101004 KB	Output is correct
13	Correct	398 ms	123040 KB	Output is correct
14	Correct	424 ms	124588 KB	Output is correct
15	Correct	608 ms	225740 KB	Output is correct
16	Correct	642 ms	227404 KB	Output is correct
17	Correct	435 ms	128992 KB	Output is correct
18	Correct	430 ms	128980 KB	Output is correct
19	Correct	613 ms	232524 KB	Output is correct
20	Correct	642 ms	232552 KB	Output is correct