Submission #238594

#	Time	Username	Problem	Language	Result	Execution time	Memory
238594		Aydarov03	Bigger segments (IZhO19_segments)	C++14	100 / 100	707 ms	35576 KiB

segments

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = (int)1e6 + 5;
const int INF = (int)1e18;
int a[N];
int tree[N * 4], lz[N * 4];
int pref[N];
int dp[N];

void mk(int &a, int other) {
  if (!a) {
    a = other;
    return;
  }
  if (dp[a - 1] == dp[other - 1]) {
    a = max(a, other);
  }
  if (dp[a - 1] < dp[other - 1]) {
    a = other;
  }
}

int get_sum(int l, int r) {
  return pref[r] - pref[l - 1];
}

void push(int v, int tl, int tr) {
  if (!lz[v]) {
    return;
  }
  if (tl != tr) {
    mk(lz[v + v], lz[v]);
    mk(lz[v + v + 1], lz[v]);
  } else {
    int x = lz[v];
    if (dp[x - 1] + 1 == dp[tl]) {
      tree[v] = max(tree[v], lz[v]);
    }
    if (dp[x - 1] + 1 > dp[tl]) {
      tree[v] = x;
      dp[tl] = dp[x - 1] + 1;
    }
  }
}

void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = N) {
  push(v, tl, tr);
  if (l <= tl && tr <= r) {
    lz[v] = val;
    push(v, tl, tr);
    return;
  }
  if (l > tr || tl > r) {
    return;
  }
  int mid = tl + tr >> 1;
  upd(l, r, val, v + v, tl, mid);
  upd(l, r, val, v + v + 1, mid + 1, tr);
}

int get(int pos, int v = 1, int tl = 1, int tr = N) {
  push(v, tl, tr);
  if (tl == tr) {
    return tree[v];
  }
  int mid = tl + tr >> 1;
  if (pos <= mid) {
    return get(pos, v + v, tl, mid);
  } else {
    return get(pos, v + v + 1, mid + 1, tr);
  }
}

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v] = 1;
    dp[tl] = 1;
    return;
  }
  int mid = tl + tr >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
}

main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    pref[i] = pref[i - 1] + a[i];
  }

  build(1, 1, n);

  for (int i = 1; i <= n; i++) {
    int best = get(i);
    int l = i, r = n + 1;
    while (r - l > 1) {
      int mid = l + r >> 1;
      if (get_sum(i + 1, mid) >= get_sum(best, i)) {
        r = mid;
      } else {
        l = mid;
      }
    }
    if (r <= n) {
      upd(r, n, i + 1);
    }
  }

  cout << dp[n];
}

Compilation message (stderr)

segments.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
segments.cpp:58:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
segments.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
segments.cpp:68:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
segments.cpp: In function 'void build(long long int, long long int, long long int)':
segments.cpp:82:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
segments.cpp: At global scope:
segments.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
segments.cpp: In function 'int main()':
segments.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int mid = l + r >> 1;
                 ~~^~~
segments.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &a[i]);
     ~~~~~^~~~~~~~~~~~~~~

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