Submission #855189

#	Time	Username	Problem	Language	Result	Execution time	Memory
855189		ooscode	Art Exhibition (JOI18_art)	C++17	100 / 100	435 ms	48084 KiB

art

// IN THE NAME OF ALLAH
// YA IMAM REZA

#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define int ll
#define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
#define test int n;cin >> n;while(n--)
#define file freopen("input.txt" , "r" , stdin); freopen("output.txt" , "w" , stdout)
#define debug while(1) cout << "TEST\n"

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii,int> piii;
typedef pair<pll , ll> plll;
 
const int N = 5e5 + 10;
const int K = 400+10;
const ll mod = 1e9+7;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

const int delta = 30103; 

int seg[N << 2];
int la[N << 2];
int n;
int a[N];
int b[N];
vector<pii> vec;

void shift(int v , int tl , int tr) {
    seg[v] += la[v];
    if(tl != tr) {
        la[v << 1] += la[v];
        la[v << 1 | 1] += la[v];
    }
    la[v] = 0;
}

void upd(int v , int tl , int tr , int l , int r , int x) {
    shift(v , tl , tr);
    if(l > r)
        return;
    if(tl == l && tr == r) {
        la[v] += x;
        shift(v , tl , tr);
        return;
    }

    kids;

    upd(cl , tl , tm , l , min(tm , r) , x);
    upd(cr , tm+1 , tr , max(l , tm+1) , r , x);

    seg[v] = max(seg[cl] , seg[cr]); 
}

int ask(int v , int tl , int tr , int l , int r) {
    shift(v , tl , tr);

    if(l > r)
        return -INF;
    if(tl == l && tr == r)
        return seg[v];
    
    kids;

    return max(ask(cl , tl , tm , l , min(tm , r)) , ask(cr , tm+1 , tr , max(l , tm+1) , r));
}

void solve() {
    cin >> n;

    for(int i = 1 ; i <= n ; i++)   
        cin >> a[i] >> b[i] , vec.pb({a[i] , b[i]});
    sort(all(vec));

    for(int i = 1 ; i <= n ; i++)
        a[i] = vec[i-1].F , b[i] = vec[i-1].S;

    int ans = -INF;

    for(int i = 1 ; i <= n ; i++) {
        // cout << a[i] << " " << b[i] << "\n";
        upd(1 , 1 , n , 1 , i , b[i]);
        upd(1 , 1 , n , 1 , i-1 , -a[i] + a[i-1]);
        ans = max(ans , ask(1 , 1 , n , 1 , i));
    }

    cout << ans << "\n";
}

signed main()
{   
    fast;
    solve();
} 

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