Submission #836591

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836591	2023-08-24T13:11:33 Z	azatega	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	454 ms	209460 KB

apple

#include <iostream>

using namespace std;

#define ll int

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

Compilation message

apple.cpp:81:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   81 | Node *root = new Node(0, 0, 1e12);
      |                             ^~~~

Subtask #1

100.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	0 ms	212 KB	Output is correct
4	Correct	26 ms	4820 KB	Output is correct
5	Correct	22 ms	5836 KB	Output is correct
6	Correct	22 ms	5716 KB	Output is correct
7	Correct	32 ms	5888 KB	Output is correct
8	Correct	187 ms	44276 KB	Output is correct
9	Correct	338 ms	75092 KB	Output is correct
10	Correct	376 ms	84856 KB	Output is correct
11	Correct	385 ms	91288 KB	Output is correct
12	Correct	357 ms	94044 KB	Output is correct
13	Correct	313 ms	108772 KB	Output is correct
14	Correct	328 ms	109824 KB	Output is correct
15	Correct	436 ms	203476 KB	Output is correct
16	Correct	430 ms	205028 KB	Output is correct
17	Correct	312 ms	115532 KB	Output is correct
18	Correct	303 ms	115768 KB	Output is correct
19	Correct	431 ms	209356 KB	Output is correct
20	Correct	454 ms	209460 KB	Output is correct