Submission #885118

#	Time	Username	Problem	Language	Result	Execution time	Memory
885118		fanwen	Sequence (APIO23_sequence)	C++17	100 / 100	1070 ms	170404 KiB

sequence

#include <bits/stdc++.h>

#define fi first 
#define se second 

using namespace std;

const int MAX = 5e5 + 5;

int A[MAX];
vector <int> pos[MAX], max_pref[MAX], min_pref[MAX], max_suff[MAX], min_suff[MAX];

struct node {
  int ma, mi, lazy;
  node(int ma = 0, int mi = 0) : ma(ma), mi(mi), lazy(0) {}
} it[MAX << 2];

node merge(const node &a, const node &b) {
  return node(max(a.ma, b.ma), min(a.mi, b.mi));
}

void build(int idx, int l, int r) {
  if(l == r) it[idx] = node(l, r);
  else {
    int mid = l + r >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
  }
}

void push(int idx) {
  if(!it[idx].lazy) return;
  it[idx << 1].ma += it[idx].lazy;
  it[idx << 1].mi += it[idx].lazy;
  it[idx << 1 | 1].ma += it[idx].lazy;
  it[idx << 1 | 1].mi += it[idx].lazy;
  it[idx << 1].lazy += it[idx].lazy;
  it[idx << 1 | 1].lazy += it[idx].lazy;
  it[idx].lazy = 0;
}

void update(int idx, int l, int r, int u, int v, int val) {
  if(l > v || r < u) return;
  if(l >= u && r <= v) {
    it[idx].ma += val;
    it[idx].mi += val;
    it[idx].lazy += val;
    return;
  }

  push(idx);

  int mid = l + r >> 1;

  update(idx << 1, l, mid, u, v, val);
  update(idx << 1 | 1, mid + 1, r, u, v, val);

  it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}

node get(int idx, int l, int r, int u, int v) {
  if(l > v || r < u) return node(-1e9, 1e9);
  if(l >= u && r <= v) return it[idx];

  push(idx);

  int mid = l + r >> 1;

  return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}

int sequence(int n, vector <int> a) {
  for (int i = 0; i < n; ++i) A[i + 1] = a[i];
  for (int i = 1; i <= n; ++i) pos[A[i]].push_back(i);
  // for (int i = 1; i <= n; ++i) cout << A[i] << " \n"[i == n];
  build(1, 0, n);
  for (int i = 1; i <= n; ++i) {
    for (auto &j : pos[i]) {
      min_pref[i].push_back(get(1, 0, n, 0, j - 1).mi);
      max_suff[i].push_back(get(1, 0, n, j, n).ma);
    }

    for (auto &j : pos[i]) update(1, 0, n, j, n, -2);

    for (auto &j : pos[i]) {
      min_suff[i].push_back(get(1, 0, n, j, n).mi);
      max_pref[i].push_back(get(1, 0, n, 0, j - 1).ma);
    }
  }
  auto check = [&] (int res) -> bool {
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j + res - 1 < (int) pos[i].size(); ++j) {
        if(max_pref[i][j] >= min_suff[i][j + res - 1] && max_suff[i][j + res - 1] >= min_pref[i][j]) {
          return true;
        }
      }
    }
    return false;
  };

  int l = -1, r = n + 1;
  // for (auto x : max_pref[1]) cout << x << " "; cout << '\n';
  // for (auto x : min_pref[1]) cout << x << " "; cout << '\n';
  // for (auto x : max_suff[1]) cout << x << " "; cout << '\n';
  // for (auto x : min_suff[1]) cout << x << " "; cout << '\n';
  // cout << check(3) << '\n';
  while(r - l > 1) {
    int mid = l + r >> 1;
    // cout << mid << endl;
    if(check(mid)) l = mid;
    else r = mid;
  }
  return l;
}

#ifdef local 

signed main() {
  freopen("TASK.inp", "r", stdin);
  freopen("TASK.out", "w", stdout);

  int n; cin >> n; vector <int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  cout << sequence(n, a); 
}

#endif // local 

Compilation message (stderr)

sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:109:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |     int mid = l + r >> 1;
      |               ~~^~~

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