Submission #667124

#	Time	Username	Problem	Language	Result	Execution time	Memory
667124		tatyam	Radio Towers (IOI22_towers)	C++17	14 / 100	1151 ms	65828 KiB

towers

#include <bits/stdc++.h>
using namespace std;


const int lg = 16;
int N;
vector<int> H;
struct SparseTable{
    static pair<int, int> op(pair<int, int> a, pair<int, int> b){
        return {std::min(a.first, b.first), std::max(a.second, b.second)};
    }
    vector<vector<pair<int, int>>> table;
    SparseTable(){}
    SparseTable(int N, vector<int> H): table(lg + 1, vector<pair<int, int>>(N)){
        for(int i = 0; i < N; i++) table[0][i] = {H[i], H[i]};
        for(int l = 1; l <= lg; l++) for(int i = 0; i + (1 << l) <= N; i++){
            table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << l - 1)]);
        }
    }
    pair<int, int> get(int L, int R) const {
        const int l = __lg(R - L);
        return op(table[l][L], table[l][R - (1 << l)]);
    }
} st;
vector<vector<array<array<int, 3>, 2>>> table;
bool first = 1;
void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;
    st = SparseTable(N, H);
}
void init2(int D) {
    first = 0;
    table.assign(lg + 1, vector<array<array<int, 3>, 2>>(N));
    for(int i = 0; i < N; i++){
        int ok = i + 1, ng = N + 1;
        auto check = [&](pair<int, int> x){
            return H[i] < x.first && x.second < H[i] + D;
        };
        while(ng - ok > 1){
            const int mid = (ok + ng) / 2;
            (check(st.get(i + 1, mid)) ? ok : ng) = mid; 
        }
        if(ok == N) table[0][i][0] = {N, 0, 0};
        if(H[ok] < H[i]) table[0][i][0] = {ok, 0, 0};
        else{
            assert(H[ok] >= H[i] + D);
            table[0][i][0] = {ok, 1, 0};
        }
    }
    for(int i = 0; i < N; i++){
        int ok = i + 1, ng = N + 1;
        auto check = [&](pair<int, int> x){
            return H[i] - D < x.first && x.second < H[i];
        };
        while(ng - ok > 1){
            const int mid = (ok + ng) / 2;
            (check(st.get(i + 1, mid)) ? ok : ng) = mid; 
        }
        if(ok == N) table[0][i][1] = {N, 1, 0};
        if(H[ok] > H[i]) table[0][i][1] = {ok, 1, 0};
        else{
            assert(H[ok] <= H[i] - D);
            table[0][i][1] = {ok, 0, 1};
        }
    }
    for(int l = 0; l < lg; l++) for(int i = 0; i < N; i++) for(int s = 0; s < 2; s++){
        auto [i2, s2, c2] = table[l][i][s];
        if(i2 == N){
            table[l + 1][i][s] = {i2, s2, c2};
            continue;
        }
        auto [i3, s3, c3] = table[l][i2][s2];
        table[l + 1][i][s] = {i3, s3, c2 + c3};
    }
}
int max_towers(int L, int R, int D) {
    if(first) init2(D);
    int i = L, s = 0, c = 1;
    for(int l = lg; l >= 0; l--){
        auto [i2, s2, c2] = table[l][i][s];
        if(i2 > R) continue;
        tie(i, s, c) = tuple{i2, s2, c + c2};
    }
    return c;
}

Compilation message (stderr)

towers.cpp: In constructor 'SparseTable::SparseTable(int, std::vector<int>)':
towers.cpp:17:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   17 |             table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << l - 1)]);
      |                                                                      ~~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23