Submission #774438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774438	2023-07-05T17:59:19 Z	VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	433 ms	230432 KB

apple

#include <iostream>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pii pair<int, int>
#define pll pair<long long, long long>
#define debug(x) cout << #x << " = " << x << endl
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int mod = 1e9 + 7;
using namespace std;
 
void setIO() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
}
 
struct Node {
    int sum, lazy;
    Node *l, *r;
 
    Node() {
        sum = 0, lazy = 0;
        l = nullptr, r = nullptr;
    }
 
    ~Node() {
        delete l;
        delete r;
    }
 
    void extend(int tl, int tr) {
        if(tl == tr) return ;
        if(this->l == nullptr) this->l = new Node();
        if(this->r == nullptr) this->r = new Node();
    }
 
    void push(int tl, int tr) {
        if(this->lazy == 0) return ;
        this->sum = (tr - tl + 1) * this->lazy;
 
        if(tl != tr) {
            extend(tl, tr);
            this->l->lazy = this->lazy;
            this->r->lazy = this->lazy;
        }
 
        this->lazy = 0;
    }
};
 
Node *root = new Node();
 
void update(Node *root, int tl, int tr, int l, int r, short val) {
    root->push(tl, tr);
    if(tl > r || l > tr || tl > tr) return ;
 
    if(l <= tl && tr <= r) {
        root->lazy = val;
        root->push(tl, tr);
        return ;
    }
 
    root->extend(tl, tr);
    int tm = (tl + tr) / 2;
    update(root->l, tl, tm, l, r, val);
    update(root->r, tm+1, tr, l, r, val);
    root->sum = root->l->sum + root->r->sum;
}
 
ll query(Node *root, int tl, int tr, int l, int r) {
    if(r < tl || tr < l)
        return 0;
 
    root->push(tl, tr);
 
    if(l <= tl && tr <= r) return root->sum;
 
    root->extend(tl, tr);
    auto tm = (tl + tr) / 2;
    return query(root->l, tl, tm, l, r) +
    query(root->r, tm+1, tr, l, r);
}
 
int main() {
    setIO();
 
    int q;
    cin >> q;
 
    ll c = 0;
    while(q--) {
        int t, a, b;
        cin >> t >> a >> b;
 
        if(t == 1) {
            ll res = query(root, 1, 1e9, a+c, b+c);
            cout << res << '\n';
            c = res;
        } else {
            update(root, 1, 1e9, a+c, b+c, 1);
        }
    }
 
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	11 ms	5204 KB	Output is correct
5	Correct	14 ms	6244 KB	Output is correct
6	Correct	14 ms	6128 KB	Output is correct
7	Correct	13 ms	6208 KB	Output is correct
8	Correct	108 ms	46316 KB	Output is correct
9	Correct	235 ms	79144 KB	Output is correct
10	Correct	238 ms	88528 KB	Output is correct
11	Correct	257 ms	95864 KB	Output is correct
12	Correct	250 ms	99048 KB	Output is correct
13	Correct	256 ms	121076 KB	Output is correct
14	Correct	262 ms	122512 KB	Output is correct
15	Correct	419 ms	223656 KB	Output is correct
16	Correct	390 ms	225208 KB	Output is correct
17	Correct	247 ms	126892 KB	Output is correct
18	Correct	286 ms	126900 KB	Output is correct
19	Correct	420 ms	230396 KB	Output is correct
20	Correct	433 ms	230432 KB	Output is correct