Submission #957771

#	Time	Username	Problem	Language	Result	Execution time	Memory
957771		LucaIlie	Global Warming (CEOI18_glo)	C++17	48 / 100	2060 ms	186632 KiB

glo

#include <bits/stdc++.h>

using namespace std;

struct AIB {
    unordered_map<int, int> aib;

    void update( int i, int x ) {
        while ( i <= 1e9 ) {
            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 main() {
    int n, x;

    cin >> n >> x;
    for ( int i = 0; i < n; i++ ) {
        int a;
        cin >> a;

        int maxLen0 = dp0.query( a - 1 ) + 1, maxLen1 = max( dp0.query( a + x - 1 ), dp1.query( a - 1 ) ) + 1;
        dp0.update( a, maxLen0 );
        dp1.update( a, maxLen1 );
    }

    cout << max( dp0.query( 1e9 ), dp1.query( 1e9 ) );

    return 0;
}

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