Submission #989734

#	Time	Username	Problem	Language	Result	Execution time	Memory
989734		mateuszwes	Art Exhibition (JOI18_art)	C++17	100 / 100	421 ms	36824 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[2*v] += tree2[v];
    tree2[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){
            for(int j = 0; j < n; j++){
                p = k = j;
                cout << query(1, 0, base-1) << ' ';
            }
            cout << '\n';
            cout << best << '\n';
        }
    }
    
    cout << best;
    
    return 0;
}

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