Submission #836582

#	Time	Username	Problem	Language	Result	Execution time	Memory
836582		azatega	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	1 ms	212 KiB

apple

#include <iostream>

using namespace std;

#define ll long long

struct Node{
    ll val;
    ll lazy = 0; // 0 if no set, 1 if set
    ll l;
    ll r;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(){}
    Node(ll _val){
        val = _val;
    }

    Node(ll _val, ll _l, ll _r){
        val = _val;
        l = _l;
        r = _r;
    }
};

void pushdown(Node *node){
    if(node->l == node->r)
        return;

    ll mid = (node->l + node->r) / 2;
    if(node->left == nullptr)
        node->left = new Node(0, node->l, mid);
    if(node->right == nullptr)
        node->right = new Node(0, mid+1, node->r);

    if(node->lazy == 1){
        node->left->val += (node->left->r - node->left->l + 1);
        node->left->lazy = 1;
        node->right->val += (node->right->r - node->right->l + 1);
        node->right->lazy = 1;
        node->lazy = 0;
    }
}

void pushup(Node *node){
    ll val = 0;
    if(node->left != nullptr)
        val += node->left->val;
    if(node->right != nullptr)
        val += node->right->val;
    node->val = val;
}

void update(Node *node, ll ql, ll qr){
    if(node->l > qr || node->r < ql)
        return;

    if(node->l >= ql && node->r <= qr){
        node->val += (node->r - node->l + 1);
        node->lazy = 1;
        return;
    }

    pushdown(node);
    update(node->left, ql, qr);
    update(node->right, ql, qr);
    pushup(node);
}

ll query(Node *node, ll ql, ll qr){
    if(node->l > qr || node->r < ql)
        return 0;
    if(node->l >= ql && node->r <= qr)
        return node->val;

    pushdown(node);
    return query(node->left, ql, qr) + query(node->right, ql, qr);
}

Node *root = new Node(0, 0, 1e16 + 5);

int main()
{
    int T;
    cin >> T;

    ll C = 0;
    while(T--){
        ll t, l, r;
        cin >> t >> l >> r;

        l += C;
        r += C;
        if(t == 1){
            ll x = query(root, l, r);
            C = x;
            cout << x << endl;
        }else{
            update(root, l, r);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100