Submission #871748

#	Time	Username	Problem	Language	Result	Execution time	Memory
871748		andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	0 ms	348 KiB

apple

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;

#define int ll

const int kInf = 1e9;
const int kMod = 1e9 + 7;

void maxSelf(int &x, int y) {
    if(y > x) {
        x = y;
    }
}

void minSelf(int &x, int y) {
    if(y < x) {
        x = y;
    }
}

void addSelf(int &x, int y, int mod) {
    x += y;
    x %= mod;
}

int add(int x, int y, int mod) {
    addSelf(x, y, mod);
    return x;
}

struct Chtholly {
    struct Node {
        int l, r;
        mutable ll v;
        Node() {}
        Node(int l, int r = -1, ll v = 0): l(l), r(r), v(v) {}
        bool operator < (const Node &oth) const {
            return l < oth.l;
        }
    };

    int n;
    set<Node> tree;
    Chtholly() {}
    Chtholly(int n): n(n) {
        tree.emplace(0, n);
    }
    Chtholly(int n, const vector<int> &v): n(n) {
        init(v);
    }
    void init(const vector<int> &v) {
        for(int i = 0; i < n; i++) {
            tree.emplace(i, i, v[i]);
        }
        tree.emplace(n, n, 0);
    }
    set<Node>::iterator split(int x) {
        auto it = tree.lower_bound(Node(x));
        if(it != tree.end() && it->l == x) {
            return it;
        }
        // assert(it != tree.begin());
        it = prev(it);
        if(it->r < x) {
            return tree.end();
        }
        int l = it->l, r = it-> r;
        ll v = it->v;
        tree.erase(it);
        tree.emplace(l, x - 1, v);
        return tree.emplace(x, r, v).first;
    }
    void flatten(int l, int r, int v) {
        auto L = split(l), R = split(r + 1);
        tree.erase(L, R);
        tree.emplace(l, r, v);
    }
    void add(int l, int r, int v) {
        auto L = split(l), R = split(r + 1);
        while(L != R) {
            L->v += v;
            L = next(L);
        }
    }
    int query_sum(int l, int r) {
        auto L = split(l), R = split(r + 1);
        int res = 0;
        while(L != R) {
            res += L->v * (L->r - L->l + 1);
            L = next(L);
        }
        return res;
    }
    int query_max(int l, int r) {
        auto L = split(l), R = split(r + 1);
        int res = -kInf;
        while(L != R) {
            maxSelf(res, L->v);
            L = next(L);
        }
        return res;
    }
    int query_min(int l, int r) {
        auto L = split(l), R = split(r + 1);
        int res = kInf;
        while(L != R) {
            minSelf(res, L->v);
            L = next(L);
        }
        return res;
    }
    int query_kth(int l, int r, int k) {
        auto L = split(l), R = split(r + 1);
        vector<pair<int, int>> v;
        while(L != R) {
            v.emplace_back(L->v, L->r - L->l + 1);
            L = next(L);
        }
        sort(v.begin(), v.end());
        for(const auto &it: v) {
            k -= it.second;
            if(k <= 0) {
                return it.first;
            }
        }
        return v.back().first;
    }
};

int32_t main() {
#ifndef EVAL
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    Chtholly ds(1e9);
    int c = 0;
    for(int i = 0; i < n; i++) {
        int t, l, r;
        cin >> t >> l >> r;

        l += c;
        r += c;

        if(t == 2) {
            ds.flatten(l, r, 1);
        } else {
            int res = ds.query_sum(l, r);
            cout << res << '\n';
            c += res;
        }
    }
    return 0;
}

• Subtask 1: 0 / 100