Submission #257586

#	Time	Username	Problem	Language	Result	Execution time	Memory
257586		BThero	Bigger segments (IZhO19_segments)	C++17	100 / 100	1210 ms	50424 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;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

struct Node {
  Node *L, *R;
  int y;
  ll x;
  pii val, mx;
  
  Node() {
    L = R = NULL;
    x = 0;
    y = rnd();
    val = mx = mp(0, 0);
  }
  
  Node(ll x, pii val) : x(x), val(val), mx(val) {
    L = R = NULL;
    y = rnd();
  }
} *T;

void show(Node *&v) {
  if (!v) {
    return;
  }
  
  if (v -> L) {
    show(v -> L);
  }

  printf("(%lld - %d %d) ", v -> x, v -> mx.fi, v -> mx.se);
  
  if (v -> R) {
    show(v -> R);
  }
}

void showln(Node *&v) {
  show(v);
  printf("\n");
}

void recalc(Node *&v) {
  if (!v) {
    return;
  }
  
  v -> mx = v -> val;
  
  if (v -> L) {
    v -> mx = max(v -> mx, v -> L -> mx);
  }
  
  if (v -> R) {
    v -> mx = max(v -> mx, v -> R -> mx);
  }
}

void Merge(Node *&T, Node *L, Node *R) {
  recalc(L);
  recalc(R);

  if (!L) {
    T = R;
    recalc(T);
    return;
  }
  
  if (!R) {
    T = L;
    recalc(T);
    return;
  }
  
  if (L -> y > R -> y) {
    T = L;
    Merge(T -> R, T -> R, R);
  }
  else {
    T = R;
    Merge(T -> L, L, T -> L);
  }
  
  recalc(T);
}

void Split(Node *T, Node *&L, Node *&R, ll x) {
  recalc(T);

  if (!T) {
    L = R = NULL;
    return;
  }
  
  if (T -> x < x) {
    Split(T -> R, T -> R, R, x);
    L = T;
  }
  else {
    Split(T -> L, L, T -> L, x);
    R = T;
  }
  
  recalc(L);
  recalc(R);
}

void addEl(ll x, pii val) {
  //printf("ADD %lld - (%d %d)\n", x, val.fi, val.se);

  Node *L, *R, *M;
  L = R = M = NULL;
  
  Split(T, L, R, x);
  Split(R, M, R, x + 1);
  
  if (!M) {
    M = new Node(x, val);
  }
  else {
    M -> val = max(M -> val, val);
    recalc(M);
  }
  
  Merge(T, L, M);
  Merge(T, T, R);
}

pii prefMax(ll x) {
  Node *L, *R;
  L = R = NULL;
  Split(T, L, R, x + 1);
  pii ret = L -> mx;
  Merge(T, L, R);
  return ret;
}

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

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);
  addEl(0, mp(0, 0));
  
  for (int i = 1; i <= n; ++i) {
    dp[i] = prefMax(pref[i]);
    dp[i].fi++;
    dp[i].se = pref[i] - pref[dp[i].se];
    addEl(dp[i].se + pref[i], mp(dp[i].fi, 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:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
segments.cpp:166: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: 27 / 27