Submission #1033836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033836		toan2602	Art Exhibition (JOI18_art)	C++14	100 / 100	246 ms	37456 KiB

art

#include<bits/stdc++.h>

using namespace std;
#define int long long
int n;
pair<int, int> a[500005];
struct Segtree {
    int val[2000005], lazy[2000005];
    void push(int id, int l, int r) {
        val[id] += lazy[id];
        if(l != r) lazy[id*2] += lazy[id], lazy[id*2+1] += lazy[id];
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, int nw) {
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
            val[id] += nw;
            if(l != r) {
                lazy[id*2] += nw;
                lazy[id*2+1] += nw;
            }
            return;
        }
        int mid = (l + r) / 2;
        update(id*2, l, mid, u, v, nw);
        update(id*2+1, mid + 1, r, u, v, nw);
        val[id] = max(val[id*2], val[id*2+1]);
    }
} tree;
void solve() {
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second, res = max(res, a[i].second);
    sort(a+1,a+1+n);
    for (int i = 1; i <= n; i++) {
        tree.update(1, 1, n, 1, i-1, a[i].second - (a[i].first - a[i-1].first));
        tree.update(1, 1, n, i, i, a[i].second);
        res = max(res, tree.val[1]);
    }
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

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