Submission #1072488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072488		vjudge1	Radio Towers (IOI22_towers)	C++17	23 / 100	4094 ms	6352 KiB

towers

#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);
    deque <ii> 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.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 << "  ";
        // for (auto [v1, v2] : dqUp) cerr << v1 << ' ' << v2 << "  ";
        // cerr << '\n';
        // for (auto [v1, v2] : dqDw) cerr << v1 << ' ' << v2 << "  ";
        // cerr << '\n';
        // cerr << '\n';
        auto itUp = lower_bound(dqUp.begin(), dqUp.end(), ii{ ve[i]+d, 0 });
        // for (auto [v, j] : dqUp) {
        //     if (ve[j] < ve[i]+d) continue;
        //     dp[0][i] = max(dp[0][i], dpPs[1][j]+1);
        //     assert(jUp == j);
        //     break;
        // }
            if (itUp != dqUp.end()) dp[0][i] = max(dp[0][i], dpPs[1][itUp->second]+1);
        // cerr << jUp << ' ';
        auto itDw = lower_bound(dqDw.begin(), dqDw.end(), ii{ ve[i]-d, 1E9 }, [&](ii a, ii b) { return a > b; });
        // for (auto [v, j] : dqDw) {
        //     if (ve[j] > ve[i]-d) continue;
        //     dp[1][i] = max(dp[1][i], dpPs[0][j]+1);
        //     assert(jDw == j);
        //     break;
        // }
            if (itDw != dqDw.end()) dp[1][i] = max(dp[1][i], dpPs[0][itDw->second]+1);
        // cerr << '\n';
        dpPs[1][i] = max(dp[1][i], dqUp.size() ? dpPs[1][dqUp.front().second] : 0);
        dqUp.push_front({ ve[i], i });
        dpPs[0][i] = max(dp[0][i], dqDw.size() ? dpPs[0][dqDw.front().second] : 0);
        dqDw.push_front({ 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
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23