제출 #310731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310731		Leonardo_Paes	Art Exhibition (JOI18_art)	C++17	100 / 100	535 ms	26104 KiB

art

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
#define int long long
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, int 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]);
}
int32_t 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;
}

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