제출 #435703

#제출 시각아이디문제언어결과실행 시간메모리
435703MladenPFinancial Report (JOI21_financial)C++17
48 / 100
4050 ms8696 KiB
#include <bits/stdc++.h> #define MAXN 300010 #define fi first #define se second #define pii pair<int,int> #define pb push_back #define INF 1000000000 #define mid (l+r)/2 #define PRINT(x) cerr<<#x<<'='<<x<<endl; using namespace std; int R[MAXN], A[MAXN], seg[4*MAXN], dp[MAXN]; vector<pii> v; vector<int> buffer; void update(int node, int l, int r, int idx, int val) { if(l == r) { seg[node] = val; return; } if(idx <= mid) update(2*node, l, mid, idx, val); else update(2*node+1, mid+1, r, idx, val); seg[node] = max(seg[2*node], seg[2*node+1]); } int query(int node, int l, int r, int L, int R) { if(L <= l && r <= R) return seg[node]; int rez = 0; if(L <= mid) rez = max(rez, query(2*node, l, mid, L, R)); if(R > mid) rez = max(rez, query(2*node+1, mid+1, r, L, R)); return rez; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, D; cin >> N >> D; for(int i = 1; i <= N; i++) { cin >> A[i]; v.pb({A[i], -i}); } fill(seg, seg+4*MAXN, 0); sort(v.begin(), v.end()); /* for(auto xx : v) { int idx = -xx.se; PRINT(idx); R[idx] = min(N, max(idx+D, query(1, 1, N, idx, min(N, idx+D)))); update(1, 1, N, idx, R[idx]); } */ ///DEBUG BRUTE for(int i = 1; i <= N; i++) { R[i] = min(N, i+D); for(int j = i+1; j <= min(N, R[i]); j++) { if(A[j] <= A[i]) R[i] = max(R[i], min(N, j+D)); } } /// ///for(int i = 1; i <= N; i++) PRINT(R[i]); fill(seg, seg+4*MAXN, -INF); update(1, 1, N, N, 0); sort(v.rbegin(), v.rend()); for(int i = 0; i < N; i++) { int idx = -v[i].se; dp[idx] = query(1, 1, N, idx, R[idx])+1; update(1, 1, N, idx, dp[idx]); } int rez = 0; for(int i = 1; i <= N; i++) { rez = max(rez, dp[i]); } cout << rez; 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...