This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
using namespace std;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
int x[N], g[N], d[N], psg[N], psd[N], t[4 * N];
void upd( int v, int l, int r, int pos, int val ) {
if ( l == r ) {
t[v] = min( t[v], val );
return;
}
int m = (l + r) / 2;
if ( pos <= m ) {
upd( v * 2, l, m, pos, val );
}
else {
upd( v * 2 + 1, m + 1, r, pos, val );
}
t[v] = min( t[v * 2], t[v * 2 + 1] );
}
int get( int v, int l, int r, int tl, int tr ) {
if ( tl > tr ) {
return 1e9;
}
if ( tl == l && tr == r ) {
return t[v];
}
int m = (l + r) / 2;
int mn = get( v * 2, l, m, tl, min( tr, m ) );
mn = min( mn, get( v * 2 + 1, m + 1, r, max( m + 1, tl ), tr ) );
return mn;
}
int32_t main() {
speed;
for ( int i = 0; i < 4 * N; i++ ) {
t[i] = 1e9;
}
int n;
cin >> n;
for ( int i = 1; i <= n; i++ ) {
cin >> x[i] >> g[i] >> d[i];
psg[i] = psg[i - 1] + g[i];
psd[i] = psd[i - 1] + d[i];
}
int ans = 0, cnt = 1;
set < int > st;
map < int, int > mp, mp1;
for ( int i = 1; i <= n; i++ ) {
st.insert( x[i] - psd[i] );
st.insert( x[i] - psd[i - 1] );
}
for ( auto i: st ) {
// cout << i << ' ' << cnt << endl;
mp[i] = cnt++;
}
for ( int i = 1; i <= n; i++ ) {
int a = mp[x[i] - psd[i]];
upd( 1, 1, cnt, mp[x[i] - psd[i - 1]], g[i] );
// cout << "-> " << x[i] - psd[i - 1] << ' ' << mp[ x[i] - psd[i - 1] ] << endl;
// cout << i << ' ' << a << ' ' << get( 1, 1, cnt, a, cnt ) << endl;
ans = max( ans, psg[i] - get( 1, 1, cnt, a, cnt ) );
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |