Submission #257648

#TimeUsernameProblemLanguageResultExecution timeMemory
257648BTheroBigger segments (IZhO19_segments)C++17
100 / 100
207 ms25080 KiB
// chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << endl; using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = (int)5e5 + 5; const ll INF = (ll)1e16; pair<int, ll> dp[MAXN]; ll t[MAXN << 2]; ll pref[MAXN]; int arr[MAXN]; int n; void build(int v, int tl, int tr) { if (tl == tr) { t[v] = INF; return; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); build(c1, tl, mid); build(c2, mid + 1, tr); t[v] = min(t[c1], t[c2]); } void update(int v, int tl, int tr, int p, ll x) { if (tl == tr) { t[v] = x; return; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); if (p <= mid) { update(c1, tl, mid, p, x); } else { update(c2, mid + 1, tr, p, x); } t[v] = min(t[c1], t[c2]); } int query(int v, int tl, int tr, ll lim) { if (tl == tr) { return tl; } int mid = (tl + tr) >> 1; int c1 = (v << 1), c2 = (c1 | 1); if (t[c2] <= lim) { return query(c2, mid + 1, tr, lim); } else { return query(c1, tl, mid, lim); } } void solve() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); pref[i] = pref[i - 1] + arr[i]; } for (int i = 1; i <= n; ++i) { dp[i] = mp(0, INF); } dp[0] = mp(0, 0); build(1, 0, n); update(1, 0, n, 0, 0); for (int i = 1; i <= n; ++i) { int j = query(1, 0, n, pref[i]); dp[i].fi = dp[j].fi + 1; dp[i].se = pref[i] - pref[j]; update(1, 0, n, i, dp[i].se + pref[i]); } printf("%d\n", dp[n].fi); } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

segments.cpp: In function 'void solve()':
segments.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
segments.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
#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...