Submission #1219445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219445		JooDdae	Radio Towers (IOI22_towers)	C++20	100 / 100	540 ms	51468 KiB

towers

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

#define mid ((l+r) >> 1)

struct Node {
    int l, r, s;
} t[10010010];
int tc;

int N, rt[100100], dn[100100], t2[400400];
vector<int> H, A, DL;

int update(int u, int id, int val, int l = 0, int r = N-1) {
    if(id < l || r < id) return u;

    int x = ++tc;
    t[x] = t[u], t[x].s += val;
    if(l == r) return x;

    t[x].l = update(t[x].l, id, val, l, mid);
    t[x].r = update(t[x].r, id, val, mid+1, r);
    return x;
}

int find(int u, int nl, int nr, int l = 0, int r = N-1) {
    if(!u || nr < l || r < nl) return 0;
    if(nl <= l && r <= nr) return t[u].s;
    return find(t[u].l, nl, nr, l, mid) + find(t[u].r, nl, nr, mid+1, r);
}

int find_first(int u, int nl, int l = 0, int r = N-1) {
    if(r < nl || !t[u].s) return -1;
    if(l == r) return l;

    int re = find_first(t[u].l, nl, l, mid);
    if(re != -1) return re;
    return find_first(t[u].r, nl, mid+1, r);
}

int find_last(int u, int nr, int l = 0, int r = N-1) {
    if(nr < l || !t[u].s) return -1;
    if(l == r) return l;

    int re = find_last(t[u].r, nr, mid+1, r);
    if(re != -1) return re;
    return find_last(t[u].l, nr, l, mid);
}

int build(int node = 1, int l = 0, int r = N-1) {
    if(l == r) return t2[node] = H[l];
    return t2[node] = min(build(node*2, l, mid), build(node*2+1, mid+1, r));
}

int find_min(int nl, int nr, int node = 1, int l = 0, int r = N-1) {
    if(r < nl || nr < l) return 1e9;
    if(nl <= l && r <= nr) return t2[node];
    return min(find_min(nl, nr, node*2, l, mid), find_min(nl, nr, node*2+1, mid+1, r));
}

void init(int N, vector<int> H) {
    ::N = N, ::H = H;
    A.push_back(0), A.push_back(1);
    for(int i=2;i<N;i++) {
        if((H[A.rbegin()[1]] < H[A.back()]) == (H[A.back()] < H[i])) A.pop_back();
        A.push_back(i);
    }

    priority_queue<array<int, 3>> pq;
    for(int i=0;i+1<A.size();i++) {
        pq.push({-abs(H[A[i]]-H[A[i+1]]), A[i], A[i+1]});
        if(H[A[i]] < H[A[i+1]]) dn[A[i]] = 1;
    }

    set<int> s;
    for(int i=0;i<A.size();i++) s.insert(A[i]), rt[0] = update(rt[0], A[i], 1);

    int prv = 0, dc = 0;

    while(!pq.empty()) {
        auto [c, a, b] = pq.top(); pq.pop();
        if(!s.count(a) || !s.count(b)) continue;

        int L = dc, R = dc;
        if(prv != c) R = ++dc, prv = c, DL.push_back(-c);
        rt[R] = update(rt[L], a, -1);
        rt[R] = update(rt[R], b, -1);

        s.erase(a);
        auto it = s.erase(s.find(b));
        if(it != s.begin() && it != s.end()) pq.push({-abs(H[*it] - H[*prev(it)]), *prev(it), *it});
    }

    build();
}

int max_towers(int L, int R, int D) {
    if(L+1 >= R) return 1;

    int u = lower_bound(DL.begin(), DL.end(), D) - DL.begin();
    if(u == DL.size()) return 1;

    int ans = find(rt[u], L, R);
    if(ans == 0) return 1;

    int LL = find_first(rt[u], L), RR = find_last(rt[u], R);
    ans = (ans + dn[LL]) / 2;

    if(L < LL && find_min(L, LL-1)+D <= H[LL]) ans++;
    if(RR < R && find_min(RR+1, R)+D <= H[RR]) ans++;

    return max(1, ans);
}

• 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