Submission #1008655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008655		fimh	Art Exhibition (JOI18_art)	C++14	100 / 100	279 ms	37528 KiB

art

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)a.size()

const ll N = 5e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll n;
pll a[N];

struct SegmentTree{
    ll st[N << 2], lz[N << 2];
    void apply(ll id, ll k){
        st[id] += k;
        lz[id] += k;
    }
    void push(ll id){
        apply(id << 1, lz[id]);
        apply(id << 1 | 1, lz[id]);
        lz[id] = 0;
    }
    void upd(ll id, ll l, ll r, ll u, ll v, ll x){
        if (r < u || l > v) return;
        if (u <= l && r <= v){
            apply(id, x);
            return;
        }
        push(id);
        ll mid = l + r >> 1;
        upd(id << 1, l, mid, u, v, x);
        upd(id << 1 | 1, mid + 1, r, u, v, x);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    ll get(ll id, ll l, ll r, ll u, ll v){
        if (r < u || l > v) return -inf;
        if (u <= l && r <= v) return st[id];
        push(id);
        ll mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
} st;

void Solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);
    ll ans = -inf;
    for (int i = 1; i <= n; ++i){
        st.upd(1, 1, n, 1, i, a[i].se);
        st.upd(1, 1, n, i, i, a[i].fi);
        ans = max(ans, st.get(1, 1, n, 1, i) - a[i].fi);
    }
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("FILE.inp", "r", stdin);
//    freopen("FILE.out", "w", stdout);
    ll t = 1; // cin >> t;
    while (t--) Solve();
}

Compilation message (stderr)

art.cpp: In member function 'void SegmentTree::upd(ll, ll, ll, ll, ll, ll)':
art.cpp:37:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         ll mid = l + r >> 1;
      |                  ~~^~~
art.cpp: In member function 'll SegmentTree::get(ll, ll, ll, ll, ll)':
art.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         ll mid = l + r >> 1;
      |                  ~~^~~

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