Submission #421099

#TimeUsernameProblemLanguageResultExecution timeMemory
421099MamedovFinancial Report (JOI21_financial)C++17
48 / 100
4050 ms5008 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<int, pii> #define pb push_back #define ll long long #define pll pair<ll, ll> #define ui unsigned int #define ull unsigned long long #define f first #define s second #define oo 1000000000 using namespace std; const int up = 3e5 + 5; int tree[up << 2]; void update(int node, int l, int r, int pos, int val) { if(l == r) { tree[node] = val; }else { int mid = (l + r) >> 1; if(pos <= mid) { update(node << 1, l, mid, pos, val); }else { update((node << 1) | 1, mid + 1, r, pos, val); } tree[node] = max(tree[node << 1], tree[(node << 1) | 1]); } } int Max(int node, int l, int r, int ql, int qr) { if(ql > qr || l > qr || ql > r) return 0; if(ql <= l && r <= qr) { return tree[node]; }else { int mid = (l + r) >> 1; return max(Max(node << 1, l, mid, ql, qr), Max((node << 1) | 1, mid + 1, r, ql, qr)); } } bool cmp(pii p1, pii p2) { if(p1.f == p2.f) return p1.s > p2.s; else return p1.f < p2.f; } void solve() { int n, d; cin >> n >> d; vector<pii>a(n); vector<int>dp(n, 1); for(int i = 0; i < n; ++i) { cin >> a[i].f; a[i].s = i; } vector<int>to_left(n); to_left[0] = 0; for(int i = 1; i < n; ++i) { to_left[i] = max(0, i - d); for(int j = i - 1; j >= to_left[i]; --j) { if(a[j] <= a[i]) { to_left[i] = max(0, j - d); } } } sort(a.begin(), a.end(), cmp); int res = 0; for(int i = 0; i < n; ++i) { int idx = a[i].s; dp[idx] = Max(1, 0, n - 1, to_left[idx], idx - 1) + 1; update(1, 0, n - 1, idx, dp[idx]); //cout << "for " << idx << " " << dp[idx] << '\n'; res = max(res, dp[idx]); } cout << res << '\n'; } int main() { ios_base::sync_with_stdio(false); 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...