# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
635902 | Bruteforceman | Financial Report (JOI21_financial) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>using namespace std;const int MX = 3e5 + 5; int st[MX*4];int n, D;int a[MX]; void upd(int l, int r, int id, int val, int v) { if(l==r) { st[v] = val; return; } int mid = (l+r)/2; if(id<=mid) upd(l, mid, id, val, v*2); else upd(mid+1, r, id, val, v*2+1); st[v] = max(st[v*2], st[v*2+1]);}int query(int l, int r, int L, int R, int v) { if(l>=L && r<=R) { return st[v]; } if(l>R || r<L) return 0; int mid = (l+r)/2; return max(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));}void PlayGround() { cin>>n>>D; for(int i=1; i<=n; ++i) { cin>>a[i]; } multiset<int>ms; set<pair<int,int>>bounds; int rht[n+1]; fill(rht, rht+n+1, n); for(int i=n; i>n-D; --i) { ms.insert(a[i]); } for(int i=n-D+1; i>0; --i) { int nb = *ms.begin(); int to = i+D-1; bounds.insert({nb, to}); auto it = bounds.lower_bound(make_pair(nb, to)); while(it!=bounds.begin()) { auto p = prev(it); if(p->second>it->second) { bounds.erase(p); } else if(p->second==it->second) { bounds.erase(it); break; } else break; } if(i>1) { auto it = bounds.upper_bound(make_pair(a[i-1]+1, -1)); if(it==bounds.end()) { rht[i-1] = n; } else { rht[i-1] = it->second; } ms.erase(ms.find(a[i+D-1])); ms.insert(a[i-1]); } } int Order[n+1]; iota(Order, Order+n+1, 0); sort(Order+1, Order+n+1, [&] (int i, int j) { if(a[i]!=a[j]) return a[i]>a[j]; return i<j; }); int ans = 0; for(int i=1; i<=n; ++i) { int cur = query(1, n, Order[i], rht[Order[i]], 1) + 1; upd(1, n, Order[i], cur, 1); ans = max(ans, cur); } cout<<ans<<'\n';}int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); PlayGround(); return 0;}