Submission #258435

#	Time	Username	Problem	Language	Result	Execution time	Memory
258435		SpeedOfMagic	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	256 KiB

art

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

#define int long long

struct segTree {
    const int nothing = -1e9;
    vector<int> val, lazy;
    int n;

    int f(int a, int b) { return max(a, b); }

	inline void pushdown(int cur) {
	    if (lazy[cur])
            val[cur] += lazy[cur];
		if (cur < n && lazy[cur]) {
			lazy[cur << 1] += lazy[cur];
			lazy[cur << 1 | 1] += lazy[cur];
		}
		lazy[cur] = 0;
	}

    void update(int l, int r, int value, int cur = 1, int ll = 1, int rr = 1e9) {
        rr = min(rr, n);
		pushdown(cur);
        if (l > r)
            return;
        if (l == ll && r == rr) {
			lazy[cur] = value;
			pushdown(cur);
			return;
		}

        int mid = (ll + rr) >> 1;
		update(l, min(r, mid), value, cur << 1, ll, mid);
		update(max(l, mid + 1), r, value, cur << 1 | 1, mid + 1, rr);
        val[cur] = f(val[cur << 1], val[cur << 1 | 1]);
    }

    int query(int l, int r, int cur = 1, int ll = 1, int rr = 1e9) {
        rr = min(rr, n);
		pushdown(cur);
        if (l > r)
            return nothing;
        if (l == ll && r == rr)
            return val[cur];

        int mid = (ll + rr) >> 1;
        return f(query(l, min(r, mid), cur << 1, ll, mid), query(max(l, mid + 1), r, cur << 1 | 1, mid + 1, rr));
    }

    segTree(vector<int> arr) {
        for (n = arr.size(); n & (n - 1); n++) {}
        val = vector<int>(n * 2, nothing);
		lazy = vector<int>(n * 2, 0);
        for (int i = n + arr.size() - 1; i; i--)
            val[i] = ((i < n) ? f(val[i << 1], val[i << 1 | 1]) : arr[i - n]);
    }
};

signed main() {
	int n; cin >> n;
	pair<int, int> p[n];
	for (int i = 0; i < n; ++i) {
		cin >> p[i].first >> p[i].second;
	}
	sort(p, p + n);
	vector<int> d(n);
	int s = 0;
	for (int i = 0; i < n; ++i) {
		s += p[i].second;
		d[i] = s - p[i].first;
	}
	segTree st(d);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = max(ans, st.query(i + 1, n) + p[i].first);
		st.update(i + 1, n, -p[i].second);
	}
	cout << ans << endl;
	
	return 0;
}

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