Submission #681531

#	Time	Username	Problem	Language	Result	Execution time	Memory
681531		peijar	Financial Report (JOI21_financial)	C++17	100 / 100	412 ms	58384 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct UnionFind {
  vector<int> id;
  vector<int> smallest;

  UnionFind() {}
  UnionFind(int N) {
    id.assign(N, -1);
    smallest.resize(N);
    iota(smallest.begin(), smallest.end(), 0);
  }

  int find(int u) {
    if (id[u] < 0)
      return u;
    return id[u] = find(id[u]);
  }

  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (id[u] > id[v])
      swap(u, v);
    id[u] += id[v];
    id[v] = u;
    smallest[u] = min(smallest[u], smallest[v]);
    return true;
  }
};

const int INF = 1e18;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N, D;
  cin >> N >> D;

  vector<int> A(N);
  for (int &x : A)
    cin >> x;

  vector<int> order(N);
  iota(order.begin(), order.end(), 0);

  sort(order.begin(), order.end(), [&](int i, int j) { return A[i] < A[j]; });

  set<int> starts;
  UnionFind dsu(N);
  vector<int> firstBad(N);

  int curAdded = N - 1;
  for (int i = N - 1; i >= 0; --i) {
    int x = A[order[i]];
    while (x < A[order[curAdded]]) {
      int j = order[curAdded];
      if (j and A[j - 1] > x)
        dsu.merge(j - 1, j);
      if (j + 1 < N and A[j + 1] > x)
        dsu.merge(j, j + 1);
      int id = dsu.find(j);
      if (-dsu.id[id] >= D)
        starts.insert(dsu.smallest[id]);
      curAdded--;
    }

    auto it = starts.lower_bound(order[i]);
    firstBad[order[i]] = it == starts.end() ? N : min(N, *it + D);
  }

  dbg(firstBad);

  int start = 1;
  while (start < N)
    start *= 2;
  vector<int> seg(2 * start);

  auto setPos = [&](int pos, int x) {
    pos += start;
    seg[pos] = x;
    while (pos > 1) {
      pos /= 2;
      seg[pos] = max(seg[2 * pos], seg[2 * pos + 1]);
    }
  };

  auto query = [&](int deb, int fin) {
    int ret = 0;

    deb += start, fin += start;
    while (deb < fin) {
      if (deb % 2)
        ret = max(ret, seg[deb++]);
      if (fin % 2)
        ret = max(ret, seg[--fin]);
      deb /= 2;
      fin /= 2;
    }
    return ret;
  };

  vector<int> pos(N);
  for (int i = 0; i < N; ++i)
    pos[order[i]] = i;

  vector<int> sortedA = A;
  sort(sortedA.begin(), sortedA.end());

  vector<vector<int>> toDelete(N);
  for (int i = 0; i < N; ++i)
    if (firstBad[i] < N)
      toDelete[firstBad[i]].push_back(i);

  for (int i = 0; i < N; ++i) {

    for (int j : toDelete[i])
      setPos(pos[j], 0);

    auto fin =
        lower_bound(sortedA.begin(), sortedA.end(), A[i]) - sortedA.begin();

    int LIS = query(0, fin) + 1;
    dbg(i, fin, LIS);
    setPos(pos[i], LIS);
  }
  cout << query(0, N) << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35