Submission #580492

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580492	2022-06-21T10:44:50 Z	LucaIlie	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	256 KB

apple

#include <bits/stdc++.h>

#define MIN_P 1
#define MAX_P 1000000000

using namespace std;

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

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

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

        return nod;
    }

    node *root = getNode();

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

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

        if ( l > ru || r < lu )
            return;
        if ( lu <= l && r <= ru ) {
            nod->lazy = x;
            nod->sum = nod->lazy * (r - l + 1);
            if ( l != r ) {
                if ( nod->left == NULL )
                    nod->left = getNode();
                nod->left->lazy += nod->lazy;
                if ( nod->right == NULL )
                    nod->right = getNode();
                nod->right->lazy += nod->lazy;
            }
            nod->lazy = 0;

            return;
        }

        if ( nod->left == NULL )
            nod->left = getNode();
        if ( nod->right == NULL )
            nod->right = getNode();

        update( nod->left, l, mid, lu, ru, x );
        update( nod->right, mid + 1, r, lu, ru, x );
        nod->sum = nod->left->sum + nod->right->sum;
    }
    void update( int l, int r, int x ) {
        update( root, MIN_P, MAX_P, l, r, x );
    }

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

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

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

        if ( nod->left == NULL )
            nod->left = getNode();
        if ( nod->right == NULL )
            nod->right = getNode();

        sum = query( nod->left, l, mid, lq, rq ) + query( nod->right, mid + 1, r, lq, rq );
        nod->sum = nod->left->sum + nod->right->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, 1 );
    }

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Halted	0 ms	0 KB	-