Submission #257544

#	Time	Username	Problem	Language	Result	Execution time	Memory
257544		BThero	Bigger segments (IZhO19_segments)	C++17	73 / 100	746 ms	262148 KiB

segments

// 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;

struct Node {
  Node *c1, *c2;
  pair<int, ll> mx;
  
  Node() {
    c1 = c2 = NULL;
    mx = mp(0, 0);
  }
} *root;

pair<int, ll> dp[MAXN];
ll pref[MAXN];
int arr[MAXN];
int n;

void recalc(Node *&v) {
  v -> mx = mp(0, 0);
  
  if (v -> c1) {
    v -> mx = max(v -> mx, v -> c1 -> mx);
  }
  
  if (v -> c2) {
    v -> mx = max(v -> mx, v -> c2 -> mx);
  }
}

void update(Node *&v, ll tl, ll tr, ll p, pair<int, ll> x) {
  if (!v) {
    v = new Node();
  }
  
  if (tl == tr) {
    v -> mx = max(v -> mx, x);
    return;
  }
  
  ll mid = (tl + tr) >> 1;
  
  if (p <= mid) {
    update(v -> c1, tl, mid, p, x);
  }
  else {
    update(v -> c2, mid + 1, tr, p, x);
  }
  
  recalc(v);
}

pair<int, ll> segMax(Node *&v, ll tl, ll tr, ll l, ll r) {
  if (!v || l > r || tl > r || tr < l) {
    return mp(0, 0);
  }
  
  if (l <= tl && tr <= r) {
    return v -> mx;
  }
  
  ll mid = (tl + tr) >> 1;
  return max(segMax(v -> c1, tl, mid, l, r), segMax(v -> c2, mid + 1, tr, l, r));
}

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);
  update(root, 0, INF, 0, mp(0, 0));
  
  for (int i = 1; i <= n; ++i) {
    dp[i] = segMax(root, 0, INF, 0, pref[i]);
    dp[i].fi++;
    dp[i].se = pref[i] - dp[i].se;
    update(root, 0, INF, dp[i].se + pref[i], mp(dp[i].fi, 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:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
segments.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 0 / 27