Submission #1124152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124152		VinhLuu	Sequence (APIO23_sequence)	C++20	0 / 100	214 ms	39584 KiB

sequence

#include <bits/stdc++.h>
//#include "sequence.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;

const int N = 5e5 + 5;

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

void add(int i) {
  for(; i <= n; i += i & -i) bit[i]++;
}

int get(int i) {
  int ret = 0;
  for(; i; i -= i & -i) ret += bit[i];
  return ret;
}

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);
  }

  for(int k = 1; k <= n; k ++) if(!col[k].empty()) {
    vector<int> rrh;
    int sz = col[k].size();
//    cerr << k << " " << sz << " d\n";
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      t[x] = x - 2 * get(x);
      t[x - 1] = x - 1 - 2 * get(x - 1);
    }
    for(int i = 0; i < sz; i ++) {
      int x = col[k][i];
      add(x);
      s[x] = 2 * get(x) - x;
      s[x - 1] = 2 * get(x - 1) - (x - 1);
//      cerr << x << " " << s[x] << " " << t[x] << " " << s[x - 1] << " " << t[x - 1] << " k\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 = rrh.size();
    for(int i = 1; i <= m; i ++) st[i] = sz;
    auto update = [&](int x,int val) {
      for(int i = x; i <= m; i += i & -i) st[i] = min(st[i], val);
    };
    auto query = [&](int x) {
      int ret = m;
      for(int i = x; i; i -= i & -i) ret = min(ret, st[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[c[ptr]]) - rrh.begin() + 1;
        update(tmp, c[ptr] - 1);
      }
      int tmp = lower_bound(all(rrh), t[x]) - rrh.begin() + 1;

      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
*/

//#define lpv

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