제출 #788844

#제출 시각아이디문제언어결과실행 시간메모리
788844Desh03Financial Report (JOI21_financial)C++17
100 / 100
174 ms9996 KiB
#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; } }; 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; deque<int> q; int ans = 0; for (int i = 0; i < n; i++) { if (i >= d) { int mn = q.front(); 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); while (q.size() && q.back() > a[i]) q.pop_back(); q.push_back(a[i]); if (i >= d) { pq.push(a[i - d]); if (q.size() && q.front() == a[i - d]) q.pop_front(); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...