제출 #1181530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181530		PagodePaiva	Radio Towers (IOI22_towers)	C++20	0 / 100	210 ms	8076 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
#include <vector>
#define fr first
#define sc second

using namespace std;

const int N = 100010;
int v[N];
int lf[N], rf[N], dp[N], max_dp[N], folha[N];

struct Segtree{
    pair <int, int> tree[4*N];
    pair <int, int> join(pair <int, int> a, pair <int, int> b){
        if(a.fr > b.fr) return a;
        if(a.fr < b.fr) return b;
        return a;
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = {v[l], l};
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return {-1, 0};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1,l,r, mid+1, tr));
    }
} seg;

int sou_folha[N];
int n;
int st = 1;
int nodes[N];

void build(int& node, int l, int r, int D){
    if(l > r) return;
    if(l == r){
        lf[node] = rf[node] = 0;
        dp[node] = 1;
        max_dp[node] = 0;
        folha[node] = v[l];
        node++;
        sou_folha[l] = 1;
        return;
    }
    int pos = seg.query(1, l, r, 1, n).second;
    int nd = node;
    node++;
    nodes[pos] = nd;
    if(l <= pos-1){
        lf[nd] = node;
        build(node, l, pos-1, D);
    }
    if(pos+1 <= r){
        rf[nd] = node;
        build(node, pos+1, r, D);
    }
    max_dp[nd] = max(max_dp[lf[nd]], max_dp[rf[nd]]);
    folha[nd] = min(folha[lf[nd]], folha[rf[nd]]);
    int esq = (lf[nd] != 0 ? max(max_dp[lf[nd]], (folha[lf[nd]] <= v[pos]-D ? 1 : 0)) : 0);
    int dir = (rf[nd] != 0 ? max(max_dp[rf[nd]], (folha[rf[nd]] <= v[pos]-D ? 1 : 0)) : 0);
    dp[nd] = esq+dir;
    max_dp[nd] = max(max_dp[nd], dp[nd]);
    return;
}

int pref[N];

void init(int NN, std::vector<int> h) {
    n = NN;
    for(int i = 1;i <= n;i++)
        v[i] = h[i-1];
    lf[0] = rf[0] = -1;
    dp[0] = -1e9;
    max_dp[0] = -1e9;
    folha[0] = 1e9+1;
    seg.build(1, 1, n);
    build(st, 1, n, 1);
    for(int i = 1;i <= n;i++){
        pref[i] = pref[i-1]+sou_folha[i];
    }
}

int max_towers(int L, int R, int D) {
    L++;
    R++;
    return pref[R]-pref[L-1]+(rf[nodes[L]] == 0 and sou_folha[L] == 0 ? 1 : 0);
}   

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