Submission #1221829

#TimeUsernameProblemLanguageResultExecution timeMemory
1221829ErJFinancial Report (JOI21_financial)C++20
0 / 100
40 ms20296 KiB
#include <bits/stdc++.h> #define ll long long #define vi vector<ll> #define vvi vector<vi> #define pp pair<ll, ll> #define vp vector<pp> using namespace std; vi Itree; void init(ll n){ while(n & (n - 1)) n++; Itree.resize(2*n, 0); } void update(ll ind, ll val){ ind += Itree.size() / 2; Itree[ind] = val; while(ind > 1){ ind /= 2; Itree[ind] = max(Itree[ind * 2], Itree[2*ind + 1]); } } ll get2(ll u, ll l, ll r, ll a, ll b){ if(l == a && r == b){; return Itree[u]; } ll s = (a + b) / 2; if(s >= r){ return get2(2*u, l, r, a, s); }else if(s <= l){ return get2(2*u + 1, l, r, s, b); }else{ return get2(2*u, l, s, a, s); return get2(2*u + 1, s, r, s, b); } } ll get(ll l, ll r){ return get2(1, l, r, 0, Itree.size() / 2); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); ll n, d; cin >> n >> d; vi A(n, 0); vp B(n); vi pos(n); for(int i = 0; i < n; i++){ cin >> A[i]; B[i] = {A[i], i}; } sort(B.begin(), B.end()); init(n); for(int i = 0; i < n; i++){ pos[B[i].second] = i; } vi dp(n, 0); ll ans = 0; for(int i = 0; i < n; i++){ ll x = get(0, pos[i]); dp[i] = 1 + x; update(pos[i], dp[i]); ans = max(ans, dp[i]); } cout << ans << '\n'; }
#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...