Submission #526530

#TimeUsernameProblemLanguageResultExecution timeMemory
526530Bill_00Bigger segments (IZhO19_segments)C++14
100 / 100
192 ms25224 KiB
#include <bits/stdc++.h> #define MOD 1000000007 #define ff first #define ss second #define N 500005 typedef long long ll; const ll mx = 1e9 + 100005; using namespace std; ll a[N], M[N], H[N], sum[N], mn[4 * N]; ll solve(ll id, ll l, ll r, ll val){ ll m = l + r >> 1; if(l == r) return l; if(mn[id * 2 + 1] <= val) return solve(id * 2 + 1, m + 1, r, val); else return solve(id * 2, l, m, val); } void update(ll id, ll l, ll r, ll pos, ll val){ if(l == r){ mn[id] = val; return; } ll m = l + r >> 1; if(m >= pos) update(id * 2, l, m, pos, val); else update(id * 2 + 1, m + 1, r, pos, val); mn[id] = min(mn[id * 2], mn[id * 2 + 1]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; for(ll i = 0; i <= n; i++){ update(1, 0, n, i, 1e18); } for(ll i = 1; i <= n; i++){ cin >> a[i]; sum[i] = sum[i - 1] + a[i]; ll id = solve(1, 0, n, sum[i]); H[i] = H[id] + 1; update(1, 0, n, i, sum[i] - sum[id] + sum[i]); } cout << H[n]; }

Compilation message (stderr)

segments.cpp: In function 'll solve(ll, ll, ll, ll)':
segments.cpp:12:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  ll m = l + r >> 1;
      |         ~~^~~
segments.cpp: In function 'void update(ll, ll, ll, ll, ll)':
segments.cpp:23:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  ll m = l + r >> 1;
      |         ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...