# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123553 | quangnamoiracvl_ralaidecu | Global Warming (CEOI18_glo) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define tn long long
using namespace std;
const int N=2e5+5, mod = 1e9;
struct node{
tn value;
node *lft, *rt;
node(){
value = 0;
lft = nullptr;
rt = nullptr;
}
};
node *root;
void Update( node *cur, tn l, tn r, tn point, tn value ){
if ( point > r or point < l )
return;
if ( l == r and point == l ){
cur -> value = value;
return;
}
tn mid = ( l + r ) >> 1;
if ( point <= mid ){
if ( cur -> lft == nullptr )
cur -> lft = new node;
Update( cur -> lft, l, mid, point, value );
}
else{
if ( cur -> rt == nullptr )
cur -> rt = new node;
Update( cur -> rt, mid + 1, r, point, value );
}
cur -> value = 0;
if ( cur -> lft != nullptr)
cur -> value = max( cur -> value, cur -> lft -> value);
if ( cur -> rt != nullptr )
cur -> value = max( cur -> value, cur -> rt -> value);
}
tn Get( node *cur, tn l, tn r, tn u, tn v ){
if ( l > v or r < u or cur == nullptr )
return 0;
if ( l >= u and r <= v )
return cur -> value;
tn mid = ( l + r ) >> 1;
return max( Get( cur -> lft, l, mid, u, v ), Get( cur -> rt, mid + 1, r, u, v ) );
}
void update( tn point, tn value ){
Update( root, 0, n, point, value );
}
tn get( tn l, tn r ){
return Get( root, 0, n, l, r );
}
int n,k,a[N],st[4*N], dp[N], dpv[N],l[N], b[N]; map<int,int> s;
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0); root = new node;
cin >> n >> k;
for ( int i = 1; i <= n; i++ )
cin >> a[i];
int ans = -1; vector<int> vic;
for ( int i = 1; i <= n; i++ ) {
dp[i] = get( 0, a[i] - 1 ) + 1;
ans = max( ans, dp[i]);
update( a[i],dp[i]);
vic.push_back(a[i] );
}
if ( !k ) {
cout << ans << endl;
return 0;
}
for ( auto v : vic )
update( v, 0 );
for ( int i = n; i >= 1; i-- )
{
dpv[i] = get( a[i] + 1, n ) + 1;
ans = max( ans, dp[i] + get( a[i] - k + 1, n ) );
update( a[i] , dpv[i] );
}
cout << ans;
}