Submission #1124316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124316		VinhLuu	Sequence (APIO23_sequence)	C++20	12 / 100	823 ms	46016 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
using namespace std;

//#define lpv

#ifndef lpv
#include "sequence.h"
#endif // lpv

const int N = 5e5 + 5;
const int oo = 1e9;

int n, a[N], bit[N], s[N], t[N], c[N], id[N], ans;
vector<int> col[N];

struct node {
  int lz, mx, mi;
} st[N << 2];

// 0  small - big
// 1  big - small

void build(int i,int l,int r) {
  if(l == r) {
    st[i].lz = 0;
    st[i].mx = st[i].mi = l;
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[i].lz = 0;
  st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
  st[i].mi = min(st[i << 1].mi, st[i << 1|1].mi);
}

void pro(int i,int x) {
  st[i].lz += x;
  st[i].mx += 2 * x;
  st[i].mi += 2 * x;
}

void dolz(int i) {
  if(!st[i].lz) return;
  int x = st[i].lz; st[i].lz = 0;
  pro(2 * i, x);
  pro(2 * i + 1, x);
}

void add(int i,int l,int r,int u,int v,int x) {
  if(l > r || u > v || r < u || v < l) return;
  if(u <= l && r <= v)  {
//    cerr << i << " " << l << " " << r << " " << st[i].mx << " " << st[i].mi << " before\n";
    pro(i, x);
//    cerr << i << " " << l << " " << r << " " << st[i].mx << " " << st[i].mi << " h\n";
    return ;
  }
  dolz(i);
  int mid = (l + r) / 2;
  add(i << 1, l, mid, u, v, x);
  add(i << 1|1, mid + 1, r, u, v, x);
  st[i].lz = 0;
//  cerr << i << " " << l << " " << r << " " << st[i].mx << " " << st[i].mi << " j\n";
  st[i].mx = max(st[i << 1].mx, st[i << 1|1].mx);
  st[i].mi = min(st[i << 1].mi, st[i << 1|1].mi);
}

int get_max(int i,int l,int r,int u,int v) {
  if(l > r || u > v || r < u || v < l) return -oo;
  if(u <= l && r <= v) return st[i].mx;
  dolz(i);
  int mid = (l + r) / 2;
  return max(get_max(i << 1, l, mid, u, v), get_max(i << 1|1, mid + 1, r, u, v));
}

int get_min(int i,int l,int r,int u,int v) {
  if(l > r || u > v || r < u || v < l) return oo;
  if(u <= l && r <= v) return st[i].mi;
  dolz(i);
  int mid = (l + r) / 2;
  return min(get_min(i << 1, l, mid, u, v), get_min(i << 1|1, mid + 1, r, u, v));
}

int sequence(int _n, vector<int> A) {
  n = _n;
  ans = 1;
  for(int i = 1; i <= n; i ++) {
    a[i] = A[i - 1];
    col[a[i]].push_back(i);
  }

  build(1, 0, n);

  for(int k = 1; k <= n; k ++) if(!col[k].empty()) {
    vector<int> rrh;
    int sz = col[k].size();
    vector<int> mxr, mir, mxl, mil;
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      mxr.push_back(get_max(1, 0, n, x, n));
      mil.push_back(get_min(1, 0, n, 0, x - 1));
    }
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      add(1, 0, n, x, n, -1);
    }
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      mir.push_back(get_min(1, 0, n, x, n));
      mxl.push_back(get_max(1, 0, n, 0, x - 1));
    }

    for(int i = sz - 1; i >= 0; i --) {
      while(i + ans < sz && mxr[i + ans] >= mil[i] && mir[i + ans] <= mil[i]) ++ans;
    }
  }
  return ans;
}

/*
7
1 2 3 1 2 1 3
3
9
1 1 2 3 4 3 2 1 1
2
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
3
*/

#ifdef lpv

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  int _n; cin >> _n;

  vector<int> A;

  for(int i = 1; i <= _n; i ++) {
    int x; cin >> x;
    A.push_back(x);
  }

  int result = sequence(_n, A);
  cout << result;

}

#endif // lpv

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