oj.uz

답안 #257583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257583 2020-08-04T12:36:25 Z BThero Bigger segments (IZhO19_segments) C++17
0 / 100
 1 ms 384 KB 
// 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 -> mx = max(M -> mx, val);
  }
  
  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) {
    //showln(T);
    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 solve()':
segments.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
segments.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -