제출 #989730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989730		mateuszwes	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	4692 KiB

art

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

constexpr int base = 1<<19;
constexpr int debug = 0;
constexpr ll mini = -1e18-7;

ll tree[2*base+7];
ll tree2[2*base+7];

int p, k;

void push(int v){
    tree[2*v] += tree2[v];
    tree[2*v+1] += tree2[v];
    tree2[v] = 0;
}

void add(int v, int a, int b, ll val){
    if((p > b) || (k < a)){
        return;
    }
    else if((p <= a) && (k >= b)){
        tree[v] += val;
        tree2[v] += val;
    }
    else{
        int mid = (a+b)/2;
        push(v);
        add(2*v, a, mid, val); add(2*v+1, mid+1, b, val);
        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}

ll query(int v, int a, int b){
    ll maksi = mini;
    if((p > b) || (k < a)){
        return mini;
    }
    else if((p <= a) && (k >= b)){
        return tree[v];
    }
    else{
        int mid = (a+b)/2;
        push(v);
        maksi = max(query(2*v, a, mid), query(2*v+1, mid+1, b));
        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
    return maksi;
}

vector<pair<ll,ll>> art;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        pair<ll,ll> a1; cin >> a1.F >> a1.S;
        art.pb(a1);
    }
    sort(art.begin(), art.end());
    
    //fill(tree, tree+2*base+7, mini);
    
    ll best = mini;
    
    for(int i = 0; i < n; i++){
        p = 0; k = i;
        add(1, 0, base-1, art[i].S);
        p = i;
        add(1, 0, base-1, art[i].F);
        p = 0;
        best = max(best, query(1, 0, base-1) - art[i].F);
        
        if(debug) cout << best << '\n';
    }
    
    cout << best;
    
    return 0;
}

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