Submission #1225889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225889		the_coding_pooh	Radio Towers (IOI22_towers)	C++20	14 / 100	280 ms	26028 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define uwu return

using namespace std;

#define fs first
#define sc second

#define all(x) x.begin(), x.end()

const int SIZE = 1e5 + 5, LOG_C = 19;

int sps_tbl[LOG_C][SIZE], H[SIZE];

int pos_max(int a, int b){
    if(H[a] > H[b])
        return a;
    return b;
}

void output(long long a, bool b){
    if(b)
        cerr << '\n';
    else
        cerr << a << ' ';
    return;
}

int query(int l, int r){
    int lv = __lg(r - l + 1);
    uwu pos_max(sps_tbl[lv][l], sps_tbl[lv][r - (1 << lv) + 1]);
}

bool is_leaf[SIZE];

int pref[SIZE];

vector <int> graph[SIZE];

int build_cartesian(int l, int r){
    if (l == r){
        is_leaf[l] = 1;
        return l;
    }
    int rt = query(l, r);
    if(rt == l)
        graph[rt].push_back(build_cartesian(rt + 1, r));
    else if(rt == r)
        graph[rt].push_back(build_cartesian(l, rt - 1));
    else{
        graph[rt].push_back(build_cartesian(rt + 1, r));
        graph[rt].push_back(build_cartesian(l, rt - 1));
    }
    return rt;
}

void init(int N, vector<int> _H) {
    for (int i = 0; i < N; i++){
        sps_tbl[0][i] = i;
        H[i] = _H[i];
    }
    for (int lv = 1; lv < LOG_C; lv++){
        for (int i = 0; i < N - (1 << lv) + 1; i++){
            sps_tbl[lv][i] = pos_max(sps_tbl[lv - 1][i], sps_tbl[lv - 1][i + (1 << (lv - 1))]);
        }
    }
    build_cartesian(0, N - 1);
    for (int i = 1; i <= N; i++){
        pref[i] = pref[i - 1] + is_leaf[i - 1];
    }
    uwu;
}

map <int, int> dp[SIZE];

void do_stuff(int nd, int D){
    dp[nd][H[nd]] = 1;
    for(auto i:graph[nd]){
        do_stuff(i, D);
        if(dp[i].size() > dp[nd].size())
            swap(dp[i], dp[nd]);
        int small_max = 0, big_max = 0;
        for (auto it = dp[i].begin(); it != dp[i].end(); it = dp[i].erase(it)){
            auto j = *it;
            if (j.fs <= H[nd] - D)
                small_max = max(small_max, j.sc);
            else
                break;
        }
        for (auto it = dp[nd].begin(); it != dp[nd].end(); it = dp[nd].erase(it)){
            auto j = *it;
            if (j.fs <= H[nd] - D)
                big_max = max(big_max, j.sc);
            else
                break;
        }
        dp[nd][H[nd] - D] = max(dp[nd][H[nd] - D], small_max + big_max);
        for(auto j:dp[i]){
            dp[nd][j.fs] = max(dp[nd][j.fs], j.sc);
        }
    }
    return;
}

int max_towers(int L, int R, int D) {
    if(R == L)
        uwu 1;
    int sum = pref[R + 1] - pref[L];
    if(!is_leaf[L]){
        if(graph[L].size() == 1 && graph[L][0] < L)
            sum++;
    }
    if(!is_leaf[R]){
        if(graph[R].size() == 1 && graph[R][0] > R)
            sum++;
    }
    return sum;
}

• 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