Submission #774390

#	Time	Username	Problem	Language	Result	Execution time	Memory
774390		VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	296 KiB

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(Node *root, int l, int r) {
    if(l == r) return ;
    if(root->l == nullptr) root->l = new Node();
    if(root->r == nullptr) root->r = new Node();
}

void push(Node *root, int l, int r) {
    if(root->lazy == 0) return ;
    root->sum = (r - l + 1) * root->lazy;

    if(l != r) {
        extend(root, l, r);
        root->l->lazy += root->lazy;
        root->r->lazy += root->lazy;
    }

    root->lazy = 0;
}

ll query(Node *root, int tl, int tr, int l, int r) {
    push(root, tl, tr);
    if(tl > r || l > tr || l > r) return 0;
    if(l <= tl && tr <= r) return root->sum;

    extend(root, tl, tr);
    int tm = (tl + tr) / 2;
    return query(root->l, tl, tm, l, r) + query(root->r, tm+1, tr, l, r);
}

void update(Node *root, int tl, int tr, int l, int r, int val) {
    push(root, tl, tr);
    if(tl > r || l > tr || l > r) return ;

    if(l <= tl && tr <= r) {
        root->lazy += val;
        push(root, tl, tr);
        return ;
    }

    extend(root, 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;
}

int main() {
    setIO();

    int q;
    cin >> q;

    Node *root = new Node();
    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);
        }
    }

    //cout << root->sum << '\n';
    return 0;
}

• Subtask 1: 0 / 100