제출 #788821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788821		Desh03	Financial Report (JOI21_financial)	C++17	100 / 100	173 ms	8360 KiB

Main

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

const int INF = 1E9;

struct SegmentTree {
  vector<int> T;
  int n;
  SegmentTree(int n_) : n(n_) {
    T.resize(n << 1);
  }
  void upd(int u, int x) {
    u += n;
    T[u] = max(T[u], x);
    while (u >>= 1) T[u] = max(T[u << 1], T[u << 1 | 1]);
  }
  void remove(int u) {
    for (T[u += n] = 0; u >>= 1;) T[u] = max(T[u << 1], T[u << 1 | 1]);
  }
  int qry(int l, int r) {
    int x = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) x = max(x, T[l++]);
      if (r & 1) x = max(x, T[--r]); 
    }
    return x;
  }
};

struct Fenwick {
  vector<int> F;
  int n;
  Fenwick(int n_) : n(n_) {
    F.resize(n, INF);
  }
  void upd(int x, int v) {
    for (; x < n; x |= x + 1) F[x] = min(F[x], v);
  }
  int qry(int x) {
    int s = INF;
    for (; x >= 0; x = (x & (x + 1)) - 1) s = min(s, F[x]);
    return s;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, d;
  cin >> n >> d;
  vector<int> a(n), v(n);
  for (int i = 0; i < n; i++) cin >> a[i], v[i] = a[i];
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin();
  SegmentTree T(n);
  Fenwick F(n);
  priority_queue<int, vector<int>, greater<int>> pq;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (i >= d) {
      int mn = F.qry(n - i + d - 1);
      while (pq.size()) {
        int x = pq.top();
        if (mn > x) {
          T.remove(x);
          pq.pop();
        } else break;
      }
    }
    int dp = T.qry(0, a[i]) + 1;
    T.upd(a[i], dp);
    ans = max(ans, dp);
    F.upd(n - i - 1, a[i]);
    if (i >= d) pq.push(a[i - d]);
  }
  cout << ans << '\n';
  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