Submission #799157

#	Time	Username	Problem	Language	Result	Execution time	Memory
799157		MilosMilutinovic	Sequence (APIO23_sequence)	C++17	0 / 100	2074 ms	80872 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];
int bal[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 Build(int v, int l, int r) {
  if (l == r) {
    st[v].lzy = 0;
    st[v].mn = 0;
    st[v].mx = 0;
    return;
  }
  int mid = l + r >> 1;
  Build(v * 2, l, mid);
  Build(v * 2 + 1, mid + 1, r);
}

void Modify(int v, int l, int r, int ql, int qr, int x) {
  for (int i = ql; i <= qr; i++) {
    bal[i] += x;
  }
  return;
  if (l > r || l > qr || r < ql || ql > qr) {
    return;
  }
  if (ql <= l && r <= qr) {
    st[v].lzy += x;
    st[v].mn += x;
    st[v].mx += x;
    push(v);
    return;
  }
  push(v);
  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) {
  int res = (int) -1e9;
  for (int i = ql; i <= qr; i++) {
    res = max(res, bal[i]);
  }
  return res;
  if (l > r || l > qr || r < ql || ql > qr) {
    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) {
  int res = (int) +1e9;
  for (int i = ql; i <= qr; i++) {
    res = min(res, bal[i]);
  }
  return res;
  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 BruteForce(int n, vector<int> a) {
  int ans = 0;
  for (int i = 0; i < n; i++) {
    vector<int> f(n);
    for (int j = 0; j < i; j++) {
      f[j] = (a[j] <= a[i] ? -1 : +1);
    }
    for (int j = i + 1; j < n; j++) {
      f[j] = (a[j] >= a[i] ? +1 : -1);
    }
    for (int j = 1; j < n; j++) {
      f[j] += f[j - 1];
    }
    for (int l = 0; l < n; l++) {
      int cnt = 0;
      for (int r = l; r < n; r++) {
        cnt += (a[r] == a[i]);
        if (l <= i && i <= r && abs(f[r] - (l == 0 ? 0 : f[l - 1])) <= 1) {
          ans = max(ans, cnt);
        }
      }
    }
  }
  return ans;
}

int sequence(int n, vector<int> a) {
  for (int i = 0; i < n; i++) {
    a[i]--;
  }
  //return BruteForce(n, a);
  vector<vector<int>> pos(n);
  for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
  }
  for (int i = 0; i < MAX; i++) {
    st[i].mn = (int) +1e9;
    st[i].mx = (int) -1e9;
  }
  Build(1, 0, n - 1);
  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] - 1);
      pref_mx[j] = QueryMax(1, 0, n - 1, 0, pos[v][j] - 1);
      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);
      pref_mn[j] = min(pref_mn[j], 0);
      pref_mx[j] = max(pref_mx[j], 0);
      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 Build(int, int, int)':
sequence.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'void Modify(int, int, int, int, int, int)':
sequence.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int QueryMax(int, int, int, int, int)':
sequence.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid = l + r >> 1;
      |             ~~^~~
sequence.cpp: In function 'int QueryMin(int, int, int, int, int)':
sequence.cpp:101:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   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