제출 #580515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580515		LucaIlie	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	642 ms	232552 KiB

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