oj.uz

Submission #957771

# Submission time Handle Problem Language Result Execution time Memory
957771 2024-04-04T10:03:27 Z LucaIlie Global Warming (CEOI18_glo) C++17
48 / 100
 2000 ms 186632 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 7 ms 2740 KB Output is correct
20 Correct 6 ms 2232 KB Output is correct
21 Correct 6 ms 2232 KB Output is correct
22 Correct 5 ms 1884 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 4 ms 1368 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 2 ms 600 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 186632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 75440 KB Output is correct
2 Correct 734 ms 75368 KB Output is correct
3 Correct 690 ms 75312 KB Output is correct
4 Correct 303 ms 37436 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 59 ms 4980 KB Output is correct
7 Correct 421 ms 44212 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1922 ms 142144 KB Output is correct
2 Correct 1814 ms 141836 KB Output is correct
3 Execution timed out 2045 ms 175008 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 7 ms 2740 KB Output is correct
20 Correct 6 ms 2232 KB Output is correct
21 Correct 6 ms 2232 KB Output is correct
22 Correct 5 ms 1884 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 4 ms 1368 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Execution timed out 2060 ms 186632 KB Time limit exceeded
28 Halted 0 ms 0 KB -