Submission #1123554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123554		quangnamoiracvl_ralaidecu	Global Warming (CEOI18_glo)	C++20	15 / 100	311 ms	88996 KiB

glo

#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, 1000000000, point, value );
}
tn get( tn l, tn r ){
    return Get( root, 0, 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); 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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25