| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1123545 | quangnamoiracvl_ralaidecu | Global Warming (CEOI18_glo) | C11 | 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, lazy;
node *l, * r;
node(){
lazy = 0;
value = 0;
l = nullptr;
r = 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 -> l == nullptr )
cur -> l = new node;
Update( cur -> l, l, mid, point, value );
}
else{
if ( cur -> r == nullptr )
cur -> r = new node;
Update( cur -> r, mid + 1, r, point, value );
}
cur -> value = -1e18;
if ( cur -> l != nullptr)
cur -> value = max( cur -> value, cur -> l -> value);
if ( cur -> r != nullptr )
cur -> value = max( cur -> value, cur -> r -> value);
}
tn Get( node *p, tn l, tn r, tn u, tn v ){
if ( l > v or r < u or p == nullptr )
return 0;
if ( l >= u and r <= v )
return p -> value;
tn mid = ( l + r ) >> 1;
return max( Get( p -> l, l, mid, u, v ), Get( p -> r, mid + 1, r, u, v ) );
}
void update( tn point, tn x ){
Update( root, 1, 1000000000, point, x );
}
tn get( tn l, tn r ){
return Get( root, 1, 1000000000, 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); bool cc = true; 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( 1, a[i] - 1 ) + 1;
ans = max( ans, dp[i]);
update( a[i],dp[i]);
vic.push_back(a[i] );
}
if ( !k ) {
cout << ans << "C C " << 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;
}