Submission #871761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871761	2023-11-11T12:52:22 Z	andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	72 ms	976 KB

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 - 1);
    }
    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 R = split(r + 1), L = split(l);
        tree.erase(L, R);
        tree.emplace(l, r, v);
    }
    void add(int l, int r, int v) {
        auto R = split(r + 1), L = split(l);
        while(L != R) {
            L->v += v;
            L = next(L);
        }
    }
    int query_sum(int l, int r) {
        auto R = split(r + 1), L = split(l);
        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 R = split(r + 1), L = split(l);
        int res = -kInf;
        while(L != R) {
            maxSelf(res, L->v);
            L = next(L);
        }
        return res;
    }
    int query_min(int l, int r) {
        auto R = split(r + 1), L = split(l);
        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 R = split(r + 1), L = split(l);
        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;

        l--;
        r--;

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	5 ms	348 KB	Output is correct
5	Correct	6 ms	344 KB	Output is correct
6	Correct	6 ms	472 KB	Output is correct
7	Correct	6 ms	600 KB	Output is correct
8	Correct	33 ms	540 KB	Output is correct
9	Correct	64 ms	824 KB	Output is correct
10	Correct	64 ms	596 KB	Output is correct
11	Correct	63 ms	604 KB	Output is correct
12	Correct	64 ms	592 KB	Output is correct
13	Correct	61 ms	856 KB	Output is correct
14	Correct	62 ms	688 KB	Output is correct
15	Correct	66 ms	836 KB	Output is correct
16	Correct	66 ms	904 KB	Output is correct
17	Correct	61 ms	848 KB	Output is correct
18	Correct	61 ms	852 KB	Output is correct
19	Correct	72 ms	976 KB	Output is correct
20	Correct	67 ms	800 KB	Output is correct