Submission #836589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836589	2023-08-24T13:10:34 Z	azatega	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	480 ms	262144 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);
    return query(node->left, ql, qr) + query(node->right, ql, qr);
}

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

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){
            C = query(root, l, r);
            cout << C << endl;
        }else{
            update(root, l, r);
        }
    }

    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	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	19 ms	6356 KB	Output is correct
5	Correct	28 ms	7628 KB	Output is correct
6	Correct	30 ms	7380 KB	Output is correct
7	Correct	23 ms	7636 KB	Output is correct
8	Correct	167 ms	58268 KB	Output is correct
9	Correct	326 ms	100560 KB	Output is correct
10	Correct	334 ms	111488 KB	Output is correct
11	Correct	347 ms	119944 KB	Output is correct
12	Correct	349 ms	123296 KB	Output is correct
13	Correct	326 ms	143704 KB	Output is correct
14	Correct	343 ms	145132 KB	Output is correct
15	Runtime error	480 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-