Submission #1124199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124199		VinhLuu	Sequence (APIO23_sequence)	C++20	20 / 100	903 ms	58140 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[2], mi[2];
} 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[0] = st[i].mi[0] = -l;
    st[i].mx[1] = st[i].mi[1] = l;
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[i].lz = 0;
  for(int j = 0; j <= 1; j ++) {
    st[i].mx[j] = max(st[i << 1].mx[j], st[i << 1|1].mx[j]);
    st[i].mi[j] = min(st[i << 1].mi[j], st[i << 1|1].mi[j]);
  }
}

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

void dolz(int i) {
  if(!st[i].lz) return;
  int x = st[i].lz; st[i].lz = 0;
  pro(i << 1, x);
  pro(i << 1|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)  {
    pro(i, x);
    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;
  for(int j = 0; j <= 1; j ++) {
    st[i].mx[j] = max(st[i << 1].mx[j], st[i << 1|1].mx[j]);
    st[i].mi[j] = min(st[i << 1].mi[j], st[i << 1|1].mi[j]);
  }
}

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

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

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, 1, n);

  for(int k = 1; k <= n; k ++) if(!col[k].empty()) {

//    if(k != 2) continue;

    vector<int> rrh;
    int sz = col[k].size();
    int pre = 0;
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      if(!pre) t[x - 1] = 0;
      t[x - 1] = min(t[x - 1], get_min(1, 1, n, pre, x - 1, 1));
      pre = x;
    }
    pre = n + 1;
    for(int i = sz - 1; i >= 0; i --) {
      int x = col[k][i];
      t[x] = get_max(1, 1, n, x, pre - 1, 1);
      pre = x;
    }
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      add(1, 1, n, x, n, 1);
    }
    pre = 0;
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      if(!pre) s[x - 1] = 0;
      s[x - 1] = min(s[x - 1], get_min(1, 1, n, pre, x - 1, 0));
      pre = x;
    }
//    cerr << k << " st\n";
    pre = n + 1;
    for(int i = sz - 1; i >= 0; i --) {
      int x = col[k][i];
      s[x] = get_max(1, 1, n, x, pre - 1, 0);
      pre = x;
//      cerr << x << " " << s[x] << " " << t[x] << " " << s[x - 1] << " " << t[x - 1] << " h\n";
      rrh.push_back(t[x]);
      rrh.push_back(t[x - 1]);
      c[i] = i;
      id[i] = i;
    }
    sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
    sort(c, c + sz, [&](int x,int y){return (s[col[k][x] - 1] == s[col[k][y] - 1] ? col[k][x] - 1 < col[k][y] - 1 : s[col[k][x] - 1] < s[col[k][y] - 1]);});
    sort(id, id + sz, [&](int x,int y){return (s[col[k][x]] == s[col[k][y]] ? col[k][x] < col[k][y] : s[col[k][x]] < s[col[k][y]]);});
    int ptr = -1;
    int m = (int)rrh.size();
    for(int i = 1; i <= m; i ++) bit[i] = m;
    auto update = [&](int x,int val) {
      for(int i = x; i <= m; i += i & -i) bit[i] = min(bit[i], val);
    };
    auto query = [&](int x) {
      int ret = m;
      for(int i = x; i; i -= i & -i) ret = min(ret, bit[i]);
      return ret;
    };
    for(int i = 0; i < sz; i ++) {
      int x = col[k][id[i]];
      int pos = id[i];
//      cerr << i << " " << pos << " " << x << " c\n";
      while(ptr < sz - 1 && s[col[k][c[ptr + 1]] - 1] <= s[x]) {
        ptr++;
        int tmp = lower_bound(all(rrh), t[col[k][c[ptr]] - 1]) - rrh.begin() + 1;
//        cerr << tmp << " " << c[ptr] - 1 << " " << t[c[ptr]] << " update\n";
        update(tmp, c[ptr] - 1);
      }
//      cerr << ptr << " " << c[ptr] << " u\n";
      int tmp = lower_bound(all(rrh), t[x]) - rrh.begin() + 1;
//      cerr << tmp << " " << query(tmp) << " ask\n";
      ans = max(ans, pos - query(tmp));
    }
  }



  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: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18