Submission #746393

#	Time	Username	Problem	Language	Result	Execution time	Memory
746393		Sami_Massah	Art Exhibition (JOI18_art)	C++17	50 / 100	501 ms	48524 KiB

art

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



const int maxn = 5e5 + 12;
long long n, L[maxn * 4], R[maxn * 4], mx[maxn], num[maxn * 4];
vector <pair<long long, long long>> pos;
void make_tree(int l, int r, int ind){
    int mid = (l + r) / 2;
    L[ind] = l;
    R[ind] = r;
    if(l == r)
        return;
    make_tree(l, mid, ind * 2);
    make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree(int l, int r, int u, long long k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        mx[u] += k;
        num[u] += k;
        return;
    }
    update_tree(l, r, u * 2, k);
    update_tree(l, r, u * 2 + 1, k);
    mx[u] = max(mx[u * 2], mx[u * 2 + 1]) + num[u];
}
long long get_max(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r)
        return mx[u];
    return max(get_max(l, r, u * 2), get_max(l, r, u * 2 + 1)) + num[u];
}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        long long a, b;
        cin >> a >> b;
        pos.push_back(make_pair(a, b));

    }
    sort(pos.begin(), pos.end());
    make_tree(0, n, 1);
    long long ans = 0;
    for(int i = 0; i < n; i++){
        update_tree(0, i, 1, pos[i].second);
        update_tree(i, i, 1, pos[i].first);
        ans = max(ans, get_max(0, i, 1) - pos[i].first);


    }
    cout << ans << endl;
}

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