Submission #521715

#	Time	Username	Problem	Language	Result	Execution time	Memory
521715		Soumya1	Financial Report (JOI21_financial)	C++17	100 / 100	828 ms	55616 KiB

Main

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 3e5 + 5;
int a[mxN];
int n, d;
template<typename T>
struct SegmentTree {
  vector<T> t;
  int n;
  T identity = T();
  SegmentTree() { }
  SegmentTree(int _n) : n(_n) {
    int lg = 31 - __builtin_clz(n);
    if ((1 << lg) < n) lg++;
    lg++;
    t.assign((1 << lg) + 5, identity);
  }
  void update(int x, int lx, int rx, int p, T v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mx = (lx + rx) >> 1;
    if (p <= mx) update(x << 1, lx, mx, p, v);
    else update(x << 1 | 1, mx + 1, rx, p, v);
    t[x] = max(t[x << 1], t[x << 1 | 1]);
  }
  void update(int p, T v) {
    update(1, 1, n, p, v);
  }
  T query(int x, int lx, int rx, int l, int r) {
    if (lx > r || l > rx) return identity;
    if (l <= lx && r >= rx) return t[x];
    int mx = (lx + rx) >> 1;
    return max(query(x << 1, lx, mx, l, r), query(x << 1 | 1, mx + 1, rx, l, r));
  }
  T query(int l, int r) {
    return query(1, 1, n, l, r);
  }
};
SegmentTree<int> st;
int p[mxN];
int find(int u) {
  return p[u] = (u == p[u] ? u : find(p[u]));
}
void unite(int u, int v) {
  u = find(u);
  p[v] = u;
}
void testCase() {
  cin >> n >> d;
  map<int, int> mp;
  for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]];
  int id = 1;
  for (auto &[x, y] : mp) y = id++;
  for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
  st = SegmentTree<int> (n);
  vector<int> v[n + 1], ans(n + 1);
  for (int i = 1; i <= n; i++) p[i] = i;
  for (int i = 1; i <= n; i++) v[a[i]].push_back(i);
  set<int> s;
  for (int i = 1; i <= n; i++) {
    for (int j : v[i]) {
      auto it = s.lower_bound(j);
      int x = j;
      if (it != s.begin() && *prev(it) >= j - d) {
        it--;
        x = find(*it);
      }
      ans[j] = st.query(max(1, x - d + 1), j) + 1;
    }
    for (int j : v[i]) {
      auto it = s.lower_bound(j);
      if (it != s.end() && *it <= j + d) {
        unite(j, *it);
      }
      if (it != s.begin() && *prev(it) >= j - d) {
        it--;
        unite(*it, j);
      }
      s.insert(j);
    }
    for (int j : v[i]) {
      st.update(j, ans[j]);
    }
  }
  // for (int i= 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
  cout << *max_element(ans.begin(), ans.end()) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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