제출 #1164823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164823		SmuggingSpun	송신탑 (IOI22_towers)	C++20	17 / 100	315 ms	48324 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
const int INF = 2e9;
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
struct Node{
    int cnt, l, r;
    Node(){
        this->cnt = 0;
        this->l = this->r = -1;
    }
};
int n, l_min[lim], r_min[lim], h[lim], log_v[lim], spt[lim][17];
vector<Node>st;
vector<pair<int, int>>a(1, make_pair(INF, -1));
int get_max(int l, int r){
    int k = log_v[r - l + 1];
    return max(spt[l][k], spt[r - (1 << k) + 1][k]);
}
void update(int id, int p){
    int l = 1, r = n;
    while(l < r){
        st[id].cnt++;
        int m = (l + r) >> 1;
        if(m < p){
            st.emplace_back(st[st[id].r]);
            st[id].r = int(st.size()) - 1;
            id = st[id].r;
            l = m + 1;
        }
        else{
            st.emplace_back(st[st[id].l]);
            st[id].l = int(st.size()) - 1;
            id = st[id].l;
            r = m;
        }
    }
    st[id].cnt++;
}
void build(int id = 0, int l = 1, int r = n){
    if(l == r){
        return;
    }
    st[id].l = st.size();
    st.emplace_back(Node());
    st[id].r = st.size();
    st.emplace_back(Node());
    int m = (l + r) >> 1;
    build(st[id].l, l, m);
    build(st[id].r, m + 1, r);
}
void init(int N, vector<int>H){
    log_v[0] = -1;
    for(int i = 1; i < lim; i++){
        log_v[i] = log_v[i >> 1] + 1;
    }
    n = N;
    for(int i = 0; i < n; i++){
        spt[i + 1][0] = h[i + 1] = H[i];
    }
    for(int j = 1; j < 17; j++){
        for(int i = 1; i + (1 << j) - 1 <= n; i++){
            spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
        }
    }
    stack<int>stk;
    for(int i = 1; i <= n; stk.push(i++)){
        while(!stk.empty() && h[i] < h[stk.top()]){
            stk.pop();
        }
        l_min[i] = (stk.empty() ? 0 : stk.top());
    }
    while(!stk.empty()){
        stk.pop();
    }
    for(int i = n; i > 0; stk.push(i--)){
        while(!stk.empty() && h[i] < h[stk.top()]){
            stk.pop();
        }
        r_min[i] = (stk.empty() ? n + 1 : stk.top());
    }
    for(int i = 1; i <= n; i++){
        a.emplace_back(min(l_min[i] == 0 ? INF : get_max(l_min[i] + 1, i), r_min[i] == n + 1 ? INF : get_max(i, r_min[i] - 1)) - h[i], i);
    }
    sort(a.begin(), a.end(), greater<pair<int, int>>());
    st.assign(n + 1, Node());
    build();
    for(int i = 1; i <= n; i++){
        st[i] = st[i - 1];
        update(i, a[i].second);
    }
}
int max_towers(int l, int r, int d){
    int low = 1, high = n, id = 0;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(a[mid].first >= d){
            low = (id = mid) + 1;
        }
        else{
            high = mid - 1;
        }
    }
    return st[id].cnt;
}

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