Submission #957776

#	Time	Username	Problem	Language	Result	Execution time	Memory
957776		LucaIlie	Global Warming (CEOI18_glo)	C++17	100 / 100	464 ms	24916 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;

struct AIB {
    int aib[2 * MAX_N + 1];

    void update( int i, int x ) {
        while ( i <= 2 * MAX_N ) {
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }

    int query( int i ) {
        int x = 0;
        while ( i > 0 ) {
            x = max( x, aib[i] );
            i -= (i & -i);
        }
        return x;
    }
} dp0, dp1;

int v[MAX_N + 1];
map<int, int> nrm;

int main() {
    int n, x;

    cin >> n >> x;
    for ( int i = 0; i < n; i++ ) {
        cin >> v[i];
        nrm[v[i]] = 1;
        nrm[v[i] + x] = 1;
    }

    int a = 0;
    for ( auto p: nrm )
        nrm[p.first] = ++a;

    for ( int i = 0; i < n; i++ ) {
        int maxLen0 = dp0.query( nrm[v[i]] - 1 ) + 1, maxLen1 = max( dp0.query( nrm[v[i] + x] - 1 ), dp1.query( nrm[v[i]] - 1 ) ) + 1;
        dp0.update( nrm[v[i]], maxLen0 );
        dp1.update( nrm[v[i]], maxLen1 );
    }

    cout << max( dp0.query( a ), dp1.query( a ) );

    return 0;
}

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