Submission #836587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836587	2023-08-24T13:08:51 Z	azatega	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	503 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, 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){
            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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	20 ms	6428 KB	Output is correct
5	Correct	37 ms	7744 KB	Output is correct
6	Correct	24 ms	7608 KB	Output is correct
7	Correct	25 ms	7764 KB	Output is correct
8	Correct	165 ms	59108 KB	Output is correct
9	Correct	335 ms	102588 KB	Output is correct
10	Correct	364 ms	113376 KB	Output is correct
11	Correct	356 ms	121932 KB	Output is correct
12	Correct	370 ms	125612 KB	Output is correct
13	Correct	346 ms	146088 KB	Output is correct
14	Correct	350 ms	147400 KB	Output is correct
15	Runtime error	503 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-