Submission #310732

#TimeUsernameProblemLanguageResultExecution timeMemory
310732Leonardo_PaesArt Exhibition (JOI18_art)C++17
100 / 100
529 ms24752 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
long long tree[1<<20], lazy[1<<20];
void flush(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node] += lazy[node];
    if(l!=r){
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }
    lazy[node] = 0;
}
void update(int node, int tl, int tr, int l, int r, long long v){
    flush(node, tl, tr);
    if(tl > r or tr < l) return;
    if(tl >= l and tr <= r){
        lazy[node] += v;
        flush(node, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    update(2*node, tl, mid, l, r, v);
    update(2*node+1, mid+1, tr, l, r, v);
    tree[node] = max(tree[2*node], tree[2*node+1]);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    cin >> n;
    vector<array<long long, 2>> v(n);
    for(int i=0; i<n; i++) cin >> v[i][0] >> v[i][1];
    sort(v.begin(), v.end());
    long long ans = 0;
    for(int i=0; i<n; i++){
        update(1, 1, n, 1, i+1, v[i][1]);
        update(1, 1, n, i+1, i+1, v[i][0]);
        ans = max(ans, tree[1] - v[i][0]);
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...