제출 #891302

#제출 시각아이디문제언어결과실행 시간메모리
891302loliconFinancial Report (JOI21_financial)C++14
48 / 100
4053 ms12112 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 5; vector<int> V; int A[maxn]; int n, D; void getr(vector<int> &r) { set<int> st; vector<pair<int, int>> arr; vector<int> op(n + 1), ed(n + 1); for(int i = 1; i <= n; ++i) { arr.emplace_back(A[i], -i); } sort(begin(arr), end(arr)); for(int i = 0; i < n; ++i) { int pos = -arr[i].second; op[pos] = ed[pos] = pos; auto it = st.upper_bound(pos); if(it != st.end() && op[*it] < pos) { r[pos] = *it + D; continue; } it = st.insert(pos).first; // printf("insert %d\n", pos); auto xx = next(it); r[pos] = pos + D; if(xx != st.end()) { if(*xx - pos <= D) { int ll = op[pos]; int rr = ed[*xx]; // printf("merge (%d, %d), (%d, %d)\n", op[pos], ed[pos], op[*xx], ed[*xx]); ed[ll] = rr; op[rr] = ll; r[pos] = rr + D; if(pos != ll) st.erase(pos); if(*xx != rr) st.erase(*xx); } } if(it != st.begin()) { xx = prev(it); if(pos - *xx <= D) { int ll = op[*xx]; int rr = ed[pos]; // printf("merge (%d, %d), (%d, %d)\n", op[pos], ed[pos], op[*xx], ed[*xx]); ed[ll] = rr; op[rr] = ll; if(pos != rr) st.erase(pos); if(*xx != ll) st.erase(*xx); } } } } void solve() { vector<int> dp(n + 1), r(n + 1); // for(int i = 1; i <= n; ++i) { // int lst = i; // for(int j = i; j <= n; ++j) { // if(j - lst > D) break; // if(A[j] <= A[i]) lst = j; // } // r[i] = lst + D; // } // for(int i = 1; i <= n; ++i) printf("%d%c", r[i], " \n"[i == n]); getr(r); // for(int i = 1; i <= n; ++i) printf("%d%c", r[i], " \n"[i == n]); // O(n^2) dp for(int i = 1; i <= n; ++i) { dp[i] = 1; for(int j = 1; j < i; ++j) { if(r[j] >= i && A[j] < A[i]) dp[i] = max(dp[i], dp[j] + 1); } } cout << *max_element(begin(dp), end(dp)) << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> D; for(int i = 1; i <= n; ++i) { cin >> A[i]; V.push_back(A[i]); } sort(begin(V), end(V)); for(int i = 1; i <= n; ++i) { A[i] = lower_bound(begin(V), end(V), A[i]) - begin(V) + 1; } 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...