Submission #625965

#	Time	Username	Problem	Language	Result	Execution time	Memory
625965		jtnydv25	Radio Towers (IOI22_towers)	C++17	100 / 100	1725 ms	325676 KiB

towers

// #pragma once 

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

#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

const int MAX = 1000000000;
const int LOG = 18;
struct Node{
    Node* lft, *rgt;
    int sum;
    Node(){lft = rgt = NULL; sum = 0;}
};

Node* add(Node* rt, int x, int s = 0, int e = MAX){
    Node* rt2 = new Node();
    Node* ret = rt2;
    while(true){        
        rt2->sum = (rt ? rt->sum: 0) + 1;
        if(s == e) break;
        int mid = (s + e) / 2;
        if(x <= mid){
            rt2->rgt = rt ? rt->rgt: NULL;
            rt2->lft = new Node();
            rt2 = rt2->lft;
            if(rt) rt = rt->lft;
            e = mid;
        } else{
            rt2->lft = rt ? rt->lft: NULL;
            rt2->rgt = new Node();
            rt2 = rt2->rgt;
            if(rt) rt = rt->rgt;
            s = mid + 1;
        }
    }
    return ret;
}

int getNum(Node* rt, int L, int R, int s = 0, int e = MAX){
    if(!rt) return 0;
    if(L > e || R < s) return 0;
    if(s >= L && e <= R) return rt->sum;
    int mid = (s + e) >> 1;
    return getNum(rt->lft, L, R, s, mid) + getNum(rt->rgt, L, R, mid + 1, e);
}

// 0-indexed
template<class T>
struct sparse_table{
    vector<vector<T>> arr; 
    vector<int> floorlog;
    function<T(T, T)> func;
    int n;
    sparse_table(){}
    sparse_table(vector<T> & vec, function<T(T, T)> f) : n(sz(vec)), floorlog(sz(vec) + 1), func(f){
        for(int i = 0; (1 << i) <= n; i++){
            for(int j = (1 << i); j < (1 << (i + 1)) && j <= n; j++)
                floorlog[j] = i;
        }
        arr.assign(floorlog[n] + 1, vector<T>(n));

        for(int i = n - 1; i >= 0; i--){
            arr[0][i] = vec[i];
            for(int j = 1; i + (1 << j) <= n; j++){
                arr[j][i] = func(arr[j - 1][i], arr[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int i, int j){
        int k = floorlog[j - i + 1];
        return func(arr[k][i], arr[k][j - (1 << k) + 1]);
    }
};

struct Tree{
    int n;
    vector<Node*> root_seg;
    vector<vector<int>> jump;
    vector<int> par;
    Tree(){}
    Tree(int n): n(n), par(n+1), root_seg(n+1, NULL){}
    void get_jumps(){
        root_seg[n] = new Node();
        jump.resize(LOG);
        par[n] = n;
        jump[0] = par;
        for(int i = 0; i < n; i++) if(jump[0][i] == -1) jump[0][i] = n;
        jump[0][n] = n;
        for(int j = 1; j < LOG; j++){
            jump[j].resize(n + 1);
            for(int i = 0; i <= n; i++) jump[j][i] = jump[j - 1][jump[j - 1][i]];
        }
    }
};

// global variables
vector<int> H, V;
sparse_table<int> st, st_ind;
Tree TL, TR, T0;
int n;

int getMin(int L, int R){
    if(L > R)swap(L, R);
    return st.get(L, R);
}
void init(int N, std::vector<int> HH){
    H = HH;
    H.push_back(MAX+10);
    n = N;
    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    st = sparse_table<int>(H, [](int i, int j){return min(i, j);});
    st_ind = sparse_table<int>(ids, [](int i, int j){return H[i] > H[j] ? i : j;});
    TL = Tree(n); TR = Tree(n);
    T0 = Tree(n);
    stack<int> stk;
    Node* zero = new Node();
    for(int i = 0; i < n; i++){
        while(!stk.empty() && H[stk.top()] < H[i]) stk.pop();
        TL.par[i] = stk.empty() ? -1: stk.top();
        stk.push(i);
    }

    while(!stk.empty()) stk.pop();

    for(int i = n - 1; i >= 0; i--){
        while(!stk.empty() && H[stk.top()] < H[i]) stk.pop();
        TR.par[i] = stk.empty() ? n: stk.top();
        stk.push(i);
    }

    V.resize(n);

    for(int i = 0; i < n; i++){
        int L = TL.par[i], R = TR.par[i];
        int mn = max(getMin(L + 1, i), getMin(i, R - 1));
        int D_max = max(0, H[i] - mn);
        V[i] = D_max;
        T0.root_seg[i] = add(i == 0 ? zero: T0.root_seg[i - 1], D_max);
        TL.root_seg[i] = add(TL.par[i] == -1 ? zero: TL.root_seg[TL.par[i]], D_max);
    }

    for(int i = n - 1; i >= 0; i--){
        TR.root_seg[i] = add(TR.par[i] == n ? zero: TR.root_seg[TR.par[i]], V[i]);
    }

    TL.get_jumps(); TR.get_jumps();
}

int fix_seq(const Tree& T, int mx_H, int i, int D){
    // sequence i -> par[i] -> .. till height < mx_H
    // subtract for those j in this sequence where getMin(i, j) > H[j] - D
    if(H[i] >= mx_H) return 0;
    int j = i;
    for(int k = LOG - 1; k >= 0; k--){
        int p = T.jump[k][j];
        if(H[p] < mx_H && getMin(i, p) > H[p] - D) j = p;
    }
    j = T.jump[0][j];
    return getNum(T.root_seg[i], D, MAX) - getNum(T.root_seg[j], D, MAX);
}

int max_towers(int L, int R, int D){
    int ret = 1 + getNum(T0.root_seg[R], D, MAX) - (L == 0 ? 0: getNum(T0.root_seg[L - 1], D, MAX));
    int mx = st_ind.get(L, R);
    ret -= V[mx] >= D;
    ret += H[mx] - max(getMin(L, mx), getMin(mx, R)) >= D;
    ret -= fix_seq(TR, H[mx], L, D);

    ret -= fix_seq(TL, H[mx], R, D);

    return ret;
}

Compilation message (stderr)

towers.cpp: In constructor 'Tree::Tree(int)':
towers.cpp:91:17: warning: 'Tree::par' will be initialized after [-Wreorder]
   91 |     vector<int> par;
      |                 ^~~
towers.cpp:89:19: warning:   'std::vector<Node*> Tree::root_seg' [-Wreorder]
   89 |     vector<Node*> root_seg;
      |                   ^~~~~~~~
towers.cpp:93:5: warning:   when initialized here [-Wreorder]
   93 |     Tree(int n): n(n), par(n+1), root_seg(n+1, NULL){}
      |     ^~~~
towers.cpp: In instantiation of 'sparse_table<T>::sparse_table(std::vector<_Tp>&, std::function<T(T, T)>) [with T = int]':
towers.cpp:124:66:   required from here
towers.cpp:64:9: warning: 'sparse_table<int>::n' will be initialized after [-Wreorder]
   64 |     int n;
      |         ^
towers.cpp:62:17: warning:   'std::vector<int> sparse_table<int>::floorlog' [-Wreorder]
   62 |     vector<int> floorlog;
      |                 ^~~~~~~~
towers.cpp:66:5: warning:   when initialized here [-Wreorder]
   66 |     sparse_table(vector<T> & vec, function<T(T, T)> f) : n(sz(vec)), floorlog(sz(vec) + 1), func(f){
      |     ^~~~~~~~~~~~

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