Submission #1261937

#TimeUsernameProblemLanguageResultExecution timeMemory
1261937PlayVoltzFinancial Report (JOI21_financial)C++20
5 / 100
215 ms44888 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), 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); for (auto i:ord){ dp[i]=st->query(max(i-k-1, 0ll), 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...