Submission #1033952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033952		vjudge1	Art Exhibition (JOI18_art)	C++14	100 / 100	231 ms	33300 KiB

art

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;

const int maxn = 5e5 + 5, oo = 1e18;
int st[maxn*4 + 5];

void build(int id, int l, int r, int vals[]){
    if (l == r){
        st[id] = vals[l];
        return;
    }
    int mid = (l + r)/2;
    build(id*2, l, mid, vals);
    build(id*2+1, mid+1, r, vals);
    st[id] = max(st[id*2], st[id*2+1]);
}

int get(int id, int l, int r, int ul, int ur){
    if (l > ur || r < ul) return -oo;
    if (ul <= l && r <= ur) return st[id];
    int mid = (l + r)/2;
    return max(get(id*2, l, mid, ul, ur), get(id*2+1, mid+1, r, ul, ur));
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n;
    cin >> n;
    pair<int, int> a[n+1];
    int vals[n+1] = {0};
    for (int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    sort(a+1, a+1+n);
    for (int i = 1; i <= n; i++){
        swap(a[i].fi, a[i].se);
    }
    for (int i = 2; i <= n; i++){
        a[i].fi += a[i-1].fi;
    }
    for (int i = 1; i <= n; i++){
        vals[i] = a[i].fi - a[i].se;
    }
    build(1, 1, n, vals);
    int mx = 0;
    for (int i = 1; i <= n; i++){
        mx = max(mx, get(1, 1, n, i, n) + a[i].se - a[i-1].fi);
    }
    cout << mx;
}

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