oj.uz

Submission #989730

# Submission time Handle Problem Language Result Execution time Memory
989730 2024-05-28T16:28:56 Z mateuszwes Art Exhibition (JOI18_art) C++17
0 / 100
 1 ms 4692 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4692 KB Output is correct
3 Incorrect 1 ms 4560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4692 KB Output is correct
3 Incorrect 1 ms 4560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4692 KB Output is correct
3 Incorrect 1 ms 4560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4692 KB Output is correct
3 Incorrect 1 ms 4560 KB Output isn't correct
4 Halted 0 ms 0 KB -