Submission #774426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774426	2023-07-05T17:45:22 Z	VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KB

apple

#include <bits/stdc++.h>
#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 {
    ll sum, lazy;
    Node *l, *r;

    Node() {
        sum = 0, lazy = 0;
        l = nullptr, r = nullptr;
    }

    ~Node() {
        delete l;
        delete r;
    }

    void extend(ll tl, ll tr) {
        if(tl == tr) return ;
        if(this->l == nullptr) this->l = new Node();
        if(this->r == nullptr) this->r = new Node();
    }

    void push(ll tl, ll 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, ll tl, ll tr, ll l, ll r, ll 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, ll tl, ll tr, ll l, ll 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

0 / 100.0

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