Submission #257585

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
257585	2020-08-04T12:37:57 Z	BThero	Bigger segments (IZhO19_segments)	C++17	Compilation error	0 ms	0 KB

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);
    M -> recalc();
  }
  
  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

segments.cpp: In function 'void addEl(ll, pii)':
segments.cpp:141:10: error: 'struct Node' has no member named 'recalc'
     M -> recalc();
          ^~~~~~
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]);
     ~~~~~^~~~~~~~~~~~~~~