제출 #788802

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

Main

#include <bits/stdc++.h>
 
using namespace std;
 
struct SegmentTree {
  vector<int> T;
  int n;
  SegmentTree(int n_) : n(n_) {
    T.resize(n << 1);
  }
  void upd(int u, int x) {
    for (T[u += n] = x; 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;
  }
};

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);
  priority_queue<int, vector<int>, greater<int>> pq;
  multiset<int> st;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int mn = (i == 0 ? 0 : *st.begin());
    while (pq.size()) {
      int x = pq.top();
      if (mn > x) {
        T.upd(x, 0);
        pq.pop();
      } else break;
    }
    int dp = T.qry(0, a[i]) + 1;
    T.upd(a[i], dp);
    ans = max(ans, dp);
    st.insert(a[i]);
    if (i >= d) {
      pq.push(a[i - d]);
      st.erase(st.find(a[i - d]));
    }
  }
  cout << ans << '\n';
  return 0;
}

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