Submission #1261983

#TimeUsernameProblemLanguageResultExecution timeMemory
1261983PlayVoltzFinancial Report (JOI21_financial)C++20
100 / 100
679 ms61196 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> #include <random> #include <chrono> #include <fstream> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second struct node{ int s, e, m, val; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; val=0; if (s!=e){ l = new node(s, m); r = new node(m+1, e); } } void up(int ind, int nv){ if (s==e)val=nv; else{ if (ind<=m)l->up(ind, nv); else r->up(ind, nv); val = max(l->val, r->val); } } int query(int left, int right){ if (left>right)return 0; if (s==left && e==right)return val; if (right<=m)return l->query(left, right); else if (left>m)return r->query(left, right); else return max(l->query(left, m), r->query(m+1, right)); } }*st; vector<int> vect; bool custom(int a, int b){ if (vect[a]==vect[b])return a>b; return vect[a]<vect[b]; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin>>n>>k; vect.resize(n); vector<int> dp(n, 0), ord(n); st = new node(0, n-1); for (int i=0; i<n; ++i)cin>>vect[i], ord[i]=i; sort(ord.begin(), ord.end(), custom); set<int> s, got; for (int i=0; i<n; ++i)s.insert(i); got.insert(-1); got.insert(n); for (auto i:ord){ auto it=got.lower_bound(i); int r=*it, l=*(--it); if (r-i<=k)for (auto p=s.lower_bound(i); p!=s.end()&&*p<=r;)p=s.erase(p); if (i-l<=k)for (auto p=s.lower_bound(l); p!=s.end()&&*p<=i;)p=s.erase(p); got.insert(i); it=s.lower_bound(i); dp[i]=st->query((it==s.begin()?0:*(--it)+1), i-1)+1; st->up(i, dp[i]); } cout<<*max_element(dp.begin(), dp.end()); }
#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...