제출 #717621

#제출 시각아이디문제언어결과실행 시간메모리
717621Radin_Zahedi2Financial Report (JOI21_financial)C++17
65 / 100
4038 ms334416 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O2") using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define sz(x) (int)x.size() //#define endl '\n' int n, d; const int N = 3e5 + 5; const int L = (1 << 19); int a[N]; int mini[N]; int dp[N]; set<pair<int, int>> seg[(L << 1)]; void addto(set<pair<int, int>> &s, pair<int, int> now) { s.insert(now); auto it = s.find(now); if (next(it) != s.end()) { if (it->se >= next(it)->se) { s.erase(it); return; } } while (s.find(now) != s.begin()) { auto it = s.find(now); if (it == s.end()) { throw; } if (prev(it)->se < it->se) { break; } s.erase(prev(it)); } } int best(set<pair<int, int>> &s, int a) { auto it = s.lower_bound(mp(a + 1, -(n + 1))); if (it == s.end()) { return 0; } return it->se; } void upd(int ind) { pair<int, int> now = mp(a[ind], -dp[ind]); ind += L; while (ind) { addto(seg[ind], now); ind >>= 1; } } int get(int e, int a) { e++; e += L; int ans = 0; while (e) { if (e & 1) { e--; ans = min(ans, best(seg[e], a)); } e >>= 1; } return ans; } void input() { cin >> n >> d; for (int i = 1; i <= n; i++) { cin >> a[i]; } } void cremini() { deque<int> dq; for (int i = 1; i < d; i++) { while (!dq.empty()) { if (a[dq.front()] < a[i]) { break; } dq.pop_front(); } dq.push_front(i); } for (int i = d; i <= n; i++) { while (!dq.empty()) { if (a[dq.front()] < a[i]) { break; } dq.pop_front(); } dq.push_front(i); if (dq.back() == i - d) { dq.pop_back(); } mini[i] = a[dq.back()]; } for (int i = d; i <= n; i++) { int tri = a[i]; for (int j = i - d + 1; j <= i; j++) { tri = min(tri, a[j]); } if (tri != mini[i]) { throw; } } } void solve() { cremini(); vector<int> obs; for (int i = n; i >= 1; i--) { int lobs = sz(obs), robs = -1; while (lobs - 1 != robs) { int m = (lobs + robs + 1) / 2; if (mini[obs[m]] > a[i]) { robs = m; } else { lobs = m; } } int limi = n; if (robs != -1) { limi = obs[robs]; } dp[i] = -get(limi, a[i]) + 1; upd(i); if (i + d - 1 <= n) { while (!obs.empty()) { if (mini[i + d - 1] < mini[obs.back()]) { break; } obs.pop_back(); } obs.pb(i + d - 1); } } int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i]); } cout << ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); solve(); 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...