#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |