Submission #848624

#	Time	Username	Problem	Language	Result	Execution time	Memory
848624		hntvnoi	Sequence (APIO23_sequence)	C++17	69 / 100	2021 ms	61352 KiB

sequence

#include<bits/stdc++.h>
#include "sequence.h"
using namespace std;
 
#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << x)
#define db(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
constexpr int INF = 0x3f3f3f3f;
 
#define N 500005
 
int n;
int a[N], min_i[N], max_i[N], max_j[N], min_j[N];
vector<int> pos[N];
 
template<class T>
  inline T pullmax(T a, T b) {
    return max(a, b);
  }
 
template<class T>
  inline T pullmin(T a, T b) {
    return min(a, b);
  }
 
template<class T>
  inline void maxi(T &a, T b) {
    if (a < b) a = b;
  }
 
template<class T>
  inline void add(T &a, T b) {
    a += b;
  }
  
template<class T>
  struct Segtree {
    int n; vector<T> s, lazy;
    Segtree(int n = 0): n(n) {
      s.resize(4 << __lg(n + 1));
      lazy.resize(4 << __lg(n + 1));
    }
    void propagate(int id, void add(T &a, T b)) {
      T &t = lazy[id];
      if (!t) return;
      add(s[id << 1], t);
      add(s[id << 1 | 1], t);
      add(lazy[id << 1], t);
      add(lazy[id << 1 | 1], t);
      t = 0;
    }
    void update(int id, int l, int r, int u, int v, T val, T pull(T a, T b), void add(T &a, T b)) {
      if (u <= l && r <= v) {
        add(s[id], val);
        if (l != r) add(lazy[id], val);
        return;
      }
      propagate(id, add);
      int mid = (l + r) >> 1;
      if (u <= mid && mid < v) {
        update(id << 1, l, mid, u, v, val, pull, add);
        update(id << 1 | 1, mid + 1, r, u, v, val, pull, add);
      } else if (mid < u) {
        update(id << 1 | 1, mid + 1, r, u, v, val, pull, add);
      } else update(id << 1, l, mid, u, v, val, pull, add);
      s[id] = pull(s[id << 1], s[id << 1 | 1]);
    }
    void update(int l, int r, T val, T pull(T a, T b), void add(T &a, T b)) {
      update(1, 0, n, l, r, val, pull, add);
    }
    T get(int id, int l, int r, int u, int v, T pull(T a, T b), void add(T &a, T b)) {
      if (u <= l && r <= v) return s[id];
      propagate(id, add);
      int mid = (l + r) >> 1;
      if (u <= mid && mid < v) return pull(get(id << 1, l, mid, u, v, pull, add), get(id << 1 | 1, mid + 1, r, u, v, pull, add));
      if (mid < u) return get(id << 1 | 1, mid + 1, r, u, v, pull, add);
      return get(id << 1, l, mid, u, v, pull, add);
    }
    T get(int u, int v, T pull(T a, T b), void add(T &a, T b)) {
      u = max(0, u), v = max(0, v);
      if (u > v) return INF;
      return get(1, 0, n, u, v, pull, add);
    }
  };
 
int sequence(int n, vector<int> values) {
  for (int i = 1; i <= n; ++i) {
    a[i] = values[i - 1];
    pos[a[i]].emplace_back(i);
  }
  sort(values.begin(), values.end());
  values.erase(unique(values.begin(), values.end()), values.end());
  reverse(values.begin(), values.end());
  Segtree<int> stmax(n + 1), stmin(n + 1);
  int res = 0;
  auto solve = [&](int x) {
    pos[x].emplace_back(0);
    sort(pos[x].begin(), pos[x].end());
    vector<int> vals;
    for (int i = 0; i < int(pos[x].size()); ++i) {
      int L = pos[x][i], R = n + 1;
      bool okay = 0;
      if (i < int(pos[x].size()) - 1) R = pos[x][i + 1], okay = 1;
      min_i[i] = stmin.get(L, R - 1, pullmin, add);
      max_i[i] = stmax.get(L, R - 1, pullmax, add);
      max_j[i] = stmax.get(L, R - 1, pullmax, add);
      min_j[i] = stmin.get(L, R - 1, pullmin, add);
      vals.emplace_back(min_j[i] - 2 * i);
      vals.emplace_back(max_j[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    vector<int> ordmin_i(pos[x].size()), ordmax_j(pos[x].size());
    iota(ordmin_i.begin(), ordmin_i.end(), 0);
    iota(ordmax_j.begin(), ordmax_j.end(), 0);
    sort(ordmin_i.begin(), ordmin_i.end(), [&](int i, int j) {
      return min_i[i] > min_i[j];
    });
    sort(ordmax_j.begin(), ordmax_j.end(), [&](int i, int j) {
      return max_j[i] > max_j[j];
    });
    auto ID = [&](int val) {
      return lower_bound(vals.begin(), vals.end(), val) - vals.begin() + 1;
    };
    auto IDR = [&](int val) {
      return upper_bound(vals.begin(), vals.end(), val) - vals.begin();
    };
    Segtree<int> stpos(vals.size());
    int j = 0;
    for (int i = 0; i < int(pos[x].size()); ++i) {
      int val = ordmin_i[i];
      while (j < int(pos[x].size()) && max_j[ordmax_j[j]] >= min_i[val]) {
        int pos = ordmax_j[j++];
        if (min_j[pos] != INF) {
          int l = ID(min_j[pos] - 2 * pos), r = ID(max_j[pos]);
          stpos.update(l, r, pos, pullmax, maxi);
        }
      }
      if (min_i[val] != INF) {
        int l = ID(min_i[val] - 2 * val), r = IDR(max_i[val] - 2 * val);
        int id = stpos.get(l, r, pullmax, maxi);
        if (id != INF) res = max(res, id - val);
      }
    }
  };
  for (int i = 0; i < int(values.size()); ++i) {
    int x = values[i];
    if (i == 0) {
      vector<int> pref(n + 1);
      for (int j = 1; j <= n; ++j) pref[j] = pref[j - 1] + (a[j] >= x ? 1 : -1);
      for (int j = 0; j <= n; ++j) {
        stmax.update(j, j, pref[j], pullmax, add);
        stmin.update(j, j, pref[j], pullmin, add);
      }
    } else for (int id : pos[x]) {
      stmax.update(id, n, 2, pullmax, add);
      stmin.update(id, n, 2, pullmin, add);
    }
    solve(x);
  }
  return res;
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:103:12: warning: variable 'okay' set but not used [-Wunused-but-set-variable]
  103 |       bool okay = 0;
      |            ^~~~

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