Submission #807526

#	Time	Username	Problem	Language	Result	Execution time	Memory
807526		dong_liu	Sequence (APIO23_sequence)	C++17	70 / 100	2072 ms	65184 KiB

sequence

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

typedef vector<int> vi;

namespace brute {

vi st;
int n_;

void upd(int i, int x) {
  i += n_;
  while (i) st[i] += x, i /= 2;
}
int kth(int k) {  // zero indexed
  int i = 1;
  while (i < n_)
    if (st[i * 2] > k)
      i = i * 2;
    else
      k -= st[i * 2], i = i * 2 + 1;
  return i - n_;
}

int sequence(int n, vi a) {
  for (int i = 0; i < n; i++) a[i]--;
  vector<vi> ii(n);
  for (int i = 0; i < n; i++) ii[a[i]].push_back(i);

  auto qry = [&](int x, int l, int r) -> int {
    return upper_bound(ii[x].begin(), ii[x].end(), r) -
           lower_bound(ii[x].begin(), ii[x].end(), l);
  };

  n_ = 1;
  while (n_ < n) n_ *= 2;
  st = vi(n_ * 2, 0);

  int ans = 0;
  for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
      upd(a[r], 1);
      int u = kth((r - l) / 2);
      int v = kth((r - l + 1) / 2);
      ans = max(ans, max(qry(u, l, r), qry(v, l, r)));
    }
    for (int r = l; r < n; r++) upd(a[r], -1);
  }
  return ans;
}

}  // namespace brute

const int N = 5e5, N_ = 1 << 19;

namespace D1 {

struct node {
  int minL, minR, maxL, maxR, sum;
};

node operator+(node u, node v) {
  return {min(u.minL, u.sum + v.minL), min(v.minR, v.sum + u.minR),
          max(u.maxL, u.sum + v.maxL), max(v.maxR, v.sum + u.maxR),
          u.sum + v.sum};
}

const node id = {0, 0, 0, 0, 0};

node st[N_ * 2];
int n_;

void activate(int i) {
  st[i += n_] = {-1, -1, 0, 0, -1};
  while (i /= 2) st[i] = st[i * 2] + st[i * 2 + 1];
}
node qry(int l, int r) {
  node u = id, v = id;
  for (l += n_, r += n_; l <= r; l /= 2, r /= 2) {
    if (l & 1) u = u + st[l++];
    if (~r & 1) v = st[r--] + v;
  }
  return u + v;
}
}  // namespace D1

/*
testing x
a = # a_i < x
b = # a_i = x
c = # a_i > x

condition for median = x
a ≤ (a + b + c) / 2 < a + b
a * 2 <= a + b + c < (a + b) * 2

conditions:
- a ≤ b + c => c - a + b ≥ 0
- c < a + b => c - a - b < 0

fix two x's at l, r

s1 = c - a + b
s2 = c - a - b

condition: s1 ≥ 0, s2 < 0

obviously include everything in the middle
now you want to extend this range

can only increase/decrease both s1 and s2

if s1 < 0, needs 0 ≤ Δ = -s1
if s2 ≥ 0, needs 0 ≥ Δ = -s2 - 1

[min Δ] ≤ -s2 - 1 => [min Δ] + s2 + 1 ≤ 0
[max Δ] ≥ -s1 => [max Δ] + s1 ≥ 0

[min Δ] + [c - a - b] + 1 ≤ 0
[max Δ] + [c - a + b] ≥ 0
*/

const int M_ = 1 << 20, offset = N_, INF = 1e8;

int mx[M_ * 2];
vi reset;

void upd(int i, int x) {
  reset.push_back(i);
  i += offset;
  i += M_;
  while (i) mx[i] = max(mx[i], x), i /= 2;
}
int qry(int l, int r) {
  l += offset;
  r += offset;
  int x = -INF;
  for (l += M_, r += M_; l <= r; l /= 2, r /= 2) {
    if (l & 1) x = max(x, mx[l++]);
    if (~r & 1) x = max(x, mx[r--]);
  }
  return x;
}
void clr() {
  for (int i : reset) {
    i += offset;
    i += M_;
    while (i) mx[i] = -INF, i /= 2;
  }
  vi().swap(reset);
}

int minL[N], maxL[N], minR[N], maxR[N], sumL[N], sumR[N], ans;

void dnc(int l, int r) {
  if (l < r) {
    int m = (l + r) / 2;
    dnc(l, m);
    dnc(m + 1, r);
    // cout << "--- " << l << ' ' << r << endl;
    /*
    [max Δ] + [c - a + b] ≥ 0 => right >= left
    [min Δ] + [c - a - b] + 1 ≤ 0
    */
    int sum = 0;
    vector<array<int, 3>> left, right;
    for (int i = m; i >= l; i--) {
      if (i < m) sum += sumR[i];
      int v = maxL[i] + sum + (m - i + 1);
      int u = minL[i] + sum - (m - i + 1) + 1;
      v *= -1;
      left.push_back({v, u, (m - i + 1)});
      // cout << "1) " << v << ' ' << u << ": " << m - i + 1 << '\n';
    }
    sum = 0;
    for (int i = m + 1; i <= r; i++) {
      sum += sumL[i];
      // cout << "SUM = " << sum << endl;
      int v = maxR[i] + sum + (i - m);
      int u = minR[i] + sum - (i - m);
      u *= -1;
      right.push_back({v, u, i - m});
      // cout << "2) " << v << ' ' << u << ": " << i - m << '\n';
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());
    int p = 0;
    for (auto [u, v, k] : right) {
      while (p < int(left.size()) && left[p][0] <= u) {
        upd(left[p][1], left[p][2]);
        p++;
      }
      ans = max(ans, k + qry(-offset, v));
    }
    clr();
  }
}

void solve(int n, vi a) {
  vector<vi> ii(n);
  for (int i = 0; i < n; i++) ii[a[i]].push_back(i);
  D1::n_ = 1;
  while (D1::n_ < n) D1::n_ *= 2;
  for (int i = 0; i < n; i++) D1::st[D1::n_ + i] = {0, 0, 1, 1, 1};
  for (int i = D1::n_ - 1; i > 0; i--)
    D1::st[i] = D1::st[i * 2] + D1::st[i * 2 + 1];
  for (int x = 0; x < n; x++) {
    if (ii[x].empty()) continue;

    // cout << "\t TESTING value = " << x + 1 << endl;

    int m = ii[x].size();
    for (int p = 0; p < m; p++) {
      D1::node u = D1::qry(p == 0 ? 0 : ii[x][p - 1] + 1, ii[x][p] - 1);
      D1::node v = D1::qry(ii[x][p] + 1, p == m - 1 ? n - 1 : ii[x][p + 1] - 1);
      // cout << u.sum << ' ';
      sumL[p] = u.sum;
      sumR[p] = v.sum;
      minL[p] = u.minR;
      maxL[p] = u.maxR;
      minR[p] = v.minL;
      maxR[p] = v.maxL;
    }
    // cout << '\n';
    dnc(0, m - 1);
    for (int i : ii[x]) {
      D1::activate(i);
      // cout << "TURNING " << i << " on\n";
    }
  }
}

int sequence(int n, vi a) {
  for (int i = 0; i < M_ * 2; i++) mx[i] = -INF;
  for (int i = 0; i < n; i++) a[i]--;
  ans = 1;  // self
  solve(n, a);

  // cout << endl << " REVERSING! " << endl;
  // reverse(a.begin(), a.end());
  for (int i = 0; i < n; i++) a[i] = n - a[i] - 1;
  solve(n, a);
  return ans;
}
#if 0

int main() {
  mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

  int n = 15;

  while (1) {
    vi a(n);
    // for (int &x : a) cin >> x;
    for (int &x : a) x = rng() % n + 1;
    int u = sequence(n, a);
    int v = brute::sequence(n, a);
    if (u != v) {
      cout << "BUG" << endl;
      for (int x : a) cout << x << ' ';
      cout << endl;
      cout << "GOT " << u << " EXPECTED " << v << endl;
      break;
    }
  }
}

#endif

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 0 / 18