Submission #765906

#	Time	Username	Problem	Language	Result	Execution time	Memory
765906		Owen11	Art Exhibition (JOI18_art)	C++14	100 / 100	281 ms	40520 KiB

art

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

# define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 5e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int arr[cnst];
int posi[cnst*4];

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

void build(int a, int b, int id) {
    if(a == b) {posi[id] = arr[a]; return;}
    int mid = (a+b)/2;
    build(a, mid, id*2);
    build(mid+1, b, id*2+1);
    posi[id] = merge(posi[id*2], posi[id*2+1]);
}

void update(int a, int b, int id, int pos, int val) {
    if(a == pos && b == pos) {
        posi[id] = val;
        return;
    }
    int mid =(a+b)/2;
    if(pos <= mid) update(a, mid, id*2, pos, val);
    else update(mid+1, b, id*2+1, pos, val);
    posi[id] = merge(posi[id*2], posi[id*2+1]);
}

int get(int a, int b, int id, int from, int to) {
    if(to < a || from > b) return LLONG_MIN;
    if(from <= a && b <= to) return posi[id];
    int mid = (a+b)/2;
    return merge(get(a, mid, id*2, from, to), get(mid+1, b, id*2+1, from, to));
}


void solve() {
    int n; cin >> n;

    pair<int, int> paint[n+5];

    for(int i = 1; i<=4*n; i++) posi[i] = LLONG_MIN;

    for(int i = 1; i<=n; i++) cin >> paint[i].fir >> paint[i].sec;

    int presum[n+5]; presum[0] = 0;
    sort(paint+1, paint+n+1);

    for(int i = 1; i<=n; i++) {
        presum[i] = presum[i-1]+paint[i].sec;
        // cerr << presum[i] << " " << paint[i].fir << endl;
        update(1, n, 1, i, presum[i]-paint[i].fir);
    }

    // for(int i = 1; i<=n; i++) cerr << presum[i] << " ";
    // cerr << endl;
    // for(int i = 1; i<=n; i++) cerr << get(1, n, 1, i, i) << " ";
    // cerr << endl;

    int ans = 0;
    for(int i = 1; i<=n; i++) {
        int temp = paint[i].fir-presum[i-1];
        // cerr << paint[i].fir << " " << presum[i-1] << " " << get(1, n, 1, i, n) << endl;
        temp += get(1, n, 1, i, n);
        // cerr << i << " " << temp << endl;
        ans = max(ans, temp);
    }

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

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