Submission #593527

#	Time	Username	Problem	Language	Result	Execution time	Memory
593527		no_namee	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	614 ms	230684 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 );
        } 
        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