Submission #337919

#TimeUsernameProblemLanguageResultExecution timeMemory
337919Dilshod_ImomovDivide and conquer (IZhO14_divide)C++17
100 / 100
209 ms60524 KiB
# 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 1e18; } 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] = 1e18; } 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]], psg[i - 1] ); // cout << "-> " << x[i] - psd[i - 1] << ' ' << mp[ x[i] - psd[i - 1] ] << ' ' << psg[i] << 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...