oj.uz

Submission #1072485

# Submission time Handle Problem Language Result Execution time Memory
1072485 2024-08-23T19:53:15 Z vjudge1 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 5404 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 = 1E5+16;
ll dp[2][MAXN];
ll dpPs[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);
    vii dqUp, dqDw;
    // dqUp sorted increasing
    // dqDw sorted decreasing
    for (ll i = ql; i <= qr; i++) {
        dp[0][i] = 1;
        dp[1][i] = 0;
        while (dqUp.size() && dqUp.back().first < ve[i]) dqUp.pop_back();
        while (dqDw.size() && dqDw.back().first > ve[i]) dqDw.pop_back();
        // if (j < dq.size()) dp[i] = max(dp[i], dq[j].second+1);
        // cerr << ve[i] << ": " << dp[i] << '\n';
        // cerr << "j " << j << "  ";
        // 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], dpPs[1][j]+1);
            break;
        }
        for (auto [v, j] : dqDw) {
            if (ve[i] < ve[j]+d) continue;
            dp[1][i] = max(dp[1][i], dpPs[0][j]+1);
            break;
        }
        dpPs[1][i] = max(dp[1][i], dqUp.size() ? dpPs[1][dqUp.back().second] : 0);
        dqUp.push_back({ ve[i], i });
        dpPs[0][i] = max(dp[0][i], dqDw.size() ? dpPs[0][dqDw.back().second] : 0);
        dqDw.push_back({ ve[i], i });
        // 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 Execution timed out 4043 ms 5404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '13', found: '2'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '13', found: '2'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '13', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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