oj.uz

Submission #1072475

# Submission time Handle Problem Language Result Execution time Memory
1072475 2024-08-23T19:41:00 Z vjudge1 Radio Towers (IOI22_towers) C++17
11 / 100
 17 ms 2752 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
using vi = vector <int>;

ll n, k;
vll ve;
void init (int n, vi ve) {
    ::n = n;
    k = 0;
    ::ve = vll(ve.begin(), ve.end());
    while (ve[k] < ve[k+1]) k++;
}

const ll MAXN = 2E3+16;
ll dp[2][MAXN];
// dp[0] low
// dp[1] up
int max_towers (int ql, int qr, int d) {
    // fill(dp+ql, dp+qr+1, 0);
    // cerr << d << '\n';
    // for (ll i = ql; i <= qr; i++) {
    //     ii maxN = { 0, -16 };
    //     dp[i] = 1;
    //     for (ll j = i-1; j >= ql; j--) {
    //         if (ve[i] <= maxN.first-d)
    //             if (ve[j] <= maxN.first-d) {
    //                 dp[i] = max(dp[i], dp[j]+1);
    //             }
    //         maxN = max(maxN, ii{ ve[j], j });
    //     }
    //     // cerr << ve[i] << ": " << dp[i] << '\n';
    // }
    // return *max_element(dp+ql, dp+qr+1);


    // fill(dp+ql, dp+qr+1, 0);
    deque <ii> dqUp, dqDw;
    for (ll i = ql; i <= qr; i++) {
        dp[0][i] = 1;
        dp[1][i] = 0;
        while (dqUp.size() && dqUp.front().first < ve[i]) dqUp.pop_front();
        while (dqDw.size() && dqDw.front().first > ve[i]) dqDw.pop_front();
        // if (j < dq.size()) dp[i] = max(dp[i], dq[j].second+1);
        // cerr << ve[i] << ": " << dp[i] << '\n';
        // cerr << "j " << j << "  ";
        dqUp.push_front({ ve[i], i });
        dqDw.push_front({ ve[i], i });
        // for (auto [v1, v2] : dqUp) cerr << v1 << ' ' << v2 << "  ";
        // cerr << '\n';
        // for (auto [v1, v2] : dqDw) cerr << v1 << ' ' << v2 << "  ";
        // cerr << '\n';
        // cerr << '\n';
        for (auto [v, j] : dqUp) {
            if (ve[i] > ve[j]-d) continue;
            dp[0][i] = max(dp[0][i], dp[1][j]+1);
        }
        for (auto [v, j] : dqDw) {
            if (ve[i] < ve[j]+d) continue;
            dp[1][i] = max(dp[1][i], dp[0][j]+1);
        }
        // ll j = ll(lower_bound(dqUp.begin(), dqUp.end(), ii{ ve[i]+d, 0 }) - dq.begin())+1;
        // for (ll j = i-1; j >= ql; j--) {
        //     if (ve[i] <= maxN.first-d)
        //         if (ve[j] <= maxN.first-d) dp[i] = max(dp[i], dp[j]+1);
        //     maxN = max(maxN, ii{ ve[j], j });
        // }
    }
    return (*max_element(dp[0]+ql, dp[0]+qr+1)+1)/2;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 1900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 388 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 5 ms 508 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 2 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 388 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 5 ms 508 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 2 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct
36 Runtime error 6 ms 1984 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 2752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 388 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 5 ms 508 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 2 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct
36 Runtime error 6 ms 1984 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 1900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -