Submission #798708

#	Time	Username	Problem	Language	Result	Execution time	Memory
798708		MilosMilutinovic	Sequence (APIO23_sequence)	C++17	0 / 100	2080 ms	59600 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

struct node {
  int mn;
  int mx;
  int lzy;
};

const int MAX = 4e6;

node st[MAX];

void push(int v) {
  if (v * 2 + 1 < MAX) {
    st[v * 2].lzy += st[v].lzy;
    st[v * 2].mn += st[v].lzy;
    st[v * 2].mx += st[v].lzy;
    st[v * 2 + 1].lzy += st[v].lzy;
    st[v * 2 + 1].mn += st[v].lzy;
    st[v * 2 + 1].mx += st[v].lzy;
    st[v].lzy = 0;
  }
}

void pull(int v) {
  st[v].mn = min(st[v * 2].mn, st[v * 2 + 1].mn);
  st[v].mx = max(st[v * 2].mx, st[v * 2 + 1].mx);
}

void Modify(int v, int l, int r, int ql, int qr, int x) {
  if (l > r || l > qr || r < ql) {
    return;
  }
  if (ql <= l && r <= qr) {
    st[v].lzy += x;
    st[v].mn += x;
    st[v].mx += x;
    push(v);
    return;
  }
  int mid = l + r >> 1;
  Modify(v * 2, l, mid, ql, qr, x);
  Modify(v * 2 + 1, mid + 1, r, ql, qr, x);
  pull(v);
}

int QueryMax(int v, int l, int r, int ql, int qr) {
  if (l > r || l > qr || r < ql) {
    return (int) -1e9;
  }
  if (ql <= l && r <= qr) {
    return st[v].mx;
  }
  push(v);
  int mid = l + r >> 1;
  int ans_l = QueryMax(v * 2, l, mid, ql, qr);
  int ans_r = QueryMax(v * 2 + 1, mid + 1, r, ql, qr);
  pull(v);
  return max(ans_l, ans_r);
}

int QueryMin(int v, int l, int r, int ql, int qr) {
  if (l > r || l > qr || r < ql) {
    return (int) +1e9;
  }
  if (ql <= l && r <= qr) {
    return st[v].mn;
  }
  push(v);
  int mid = l + r >> 1;
  int ans_l = QueryMin(v * 2, l, mid, ql, qr);
  int ans_r = QueryMin(v * 2 + 1, mid + 1, r, ql, qr);
  pull(v);
  return min(ans_l, ans_r);
}

int sequence(int n, vector<int> a) {
  for (int i = 0; i < n; i++) {
    a[i]--;
  }
  vector<vector<int>> pos(n);
  for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    Modify(1, 0, n - 1, i, n - 1, 1);
  }
  auto Intersect = [&](int l1, int r1, int l2, int r2) {
    int L = max(l1, l2);
    int R = min(r1, r2);
    return L <= R;
  };
  for (int v = 0; v < n; v++) {
    int sz = (int) pos[v].size();
    vector<int> pref_mn(sz);
    vector<int> pref_mx(sz);
    vector<int> suff_mn(sz);
    vector<int> suff_mx(sz);
    for (int j = 0; j < sz; j++) {
      Modify(1, 0, n - 1, pos[v][j], n - 1, -1);
      pref_mn[j] = QueryMin(1, 0, n - 1, 0, pos[v][j]);
      pref_mx[j] = QueryMax(1, 0, n - 1, 0, pos[v][j]);
      suff_mn[j] = QueryMin(1, 0, n - 1, pos[v][j], n - 1);
      suff_mx[j] = QueryMax(1, 0, n - 1, pos[v][j], n - 1);
      Modify(1, 0, n - 1, pos[v][j], n - 1, -1);
    }
    for (int x = 0; x < sz; x++) {
      for (int y = x; y < sz; y++) {
        if (Intersect(suff_mn[y] - 1, suff_mx[y] + 1, pref_mn[x], pref_mx[x])) {
          ans = max(ans, y - x + 1);
        }
      }
    }
  }
  return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void Modify(int, int, int, int, int, int)':
sequence.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int QueryMax(int, int, int, int, int)':
sequence.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int QueryMin(int, int, int, int, int)':
sequence.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid = l + r >> 1;
      |             ~~^~~

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