답안 #871760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871760	2023-11-11T12:50:50 Z	andrei_c1	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	82 ms	3020 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);
        tree.emplace(n, 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 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(2e9);
    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

#	결과	실행 시간	메모리	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	612 KB	Output is correct
5	Correct	7 ms	600 KB	Output is correct
6	Correct	7 ms	604 KB	Output is correct
7	Correct	6 ms	600 KB	Output is correct
8	Correct	34 ms	1332 KB	Output is correct
9	Correct	70 ms	2752 KB	Output is correct
10	Correct	67 ms	2564 KB	Output is correct
11	Correct	65 ms	2448 KB	Output is correct
12	Correct	70 ms	2608 KB	Output is correct
13	Correct	63 ms	2828 KB	Output is correct
14	Correct	63 ms	2760 KB	Output is correct
15	Correct	69 ms	2900 KB	Output is correct
16	Correct	82 ms	3020 KB	Output is correct
17	Correct	69 ms	2860 KB	Output is correct
18	Correct	63 ms	2972 KB	Output is correct
19	Correct	68 ms	2900 KB	Output is correct
20	Correct	74 ms	2896 KB	Output is correct