Submission #1231108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231108		namskibiditoilet694	Art Exhibition (JOI18_art)	C++20	100 / 100	358 ms	31732 KiB

art

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    int n;
    vector<ll> st;
    SegTree(int _n) : n(_n), st(4 * n, LLONG_MAX) {}
    void build(int p, int l, int r, const vector<ll> &a) {
        if (l == r) st[p] = a[l];
        else {
            int m = (l + r) >> 1;
            build(p << 1, l, m, a);
            build(p << 1 | 1, m + 1, r, a);
            st[p] = min(st[p << 1], st[p << 1 | 1]);
        }
    }
    ll query(int p, int l, int r, int i, int j) {
        if (j < l || r < i) return LLONG_MAX;
        if (i <= l && r <= j) return st[p];
        int m = (l + r) >> 1;
        return min(query(p << 1, l, m, i, j), query(p << 1 | 1, m + 1, r, i, j));
    }
};

int main() {
    int n; cin >> n; 
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end(), [](auto &x, auto &y) { return x.first < y.first; });

    vector<ll> p(n + 1);
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i - 1].second;

    vector<ll> m(n + 1);
    for (int i = 1; i <= n; i++) m[i] = p[i - 1] - a[i - 1].first;

    SegTree st(n + 1);
    st.build(1, 1, n, m);

    ll ans = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        ll m1 = st.query(1, 1, n, 1, i);
        ll m2 = (p[i] - a[i - 1].first) - m1;
        ans = max(ans, m2);
    }
    cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50