Submission #836555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836555	2023-08-24T12:53:08 Z	azatega	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	1 ms	212 KB

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);

    ll res = 0;
    if(node->left != nullptr)
        res += query(node->left, ql, qr);
    if(node->right != nullptr)
        res += query(node->right, ql, qr);
    return res;
}

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

int main()
{
    int T;
    cin >> T;
    while(T--){
        ll t, l, r;
        cin >> t >> l >> r;

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

    return 0;
}

Subtask #1

0 / 100.0

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