Submission #1219439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219439		JooDdae	Radio Towers (IOI22_towers)	C++20	0 / 100	824 ms	33632 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];
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 = nl, r = N-1;
    while(l <= r) {
        if(find(u, nl, mid)) r = mid-1;
        else l = mid+1;
    }
    return l;
}

int find_last(int u, int nr) {
    int l = 0, r = nr;
    while(l <= r) {
        if(find(u, mid, nr)) l = mid+1;
        else r = mid-1;
    }
    return 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]});
    }

    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);

        // cout << L << " " << R << " " << find(rt[R], 0, N-1) << "\n";

        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});
    }
}

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;
    ans = (ans + 1) / 2;

    int LL = find_first(rt[u], L), RR = find_last(rt[u], R);

    // cout << u << " " << find(rt[u], 0, N-1) << " " << ans << "]\n";
    // cout << LL << " " << RR << "\n";
    
    auto it = lower_bound(A.begin(), A.end(), L);
    if(it != A.end() && *it < LL && H[*it]+D <= H[LL]) ans++;
    else if(++it != A.end() && *it < LL && H[*it]+D <= H[LL]) ans++;
    else if(L < LL & H[L]+D <= H[LL]) ans++;

    it = upper_bound(A.begin(), A.end(), R);
    if(prev(it) != A.begin()){
        it--;
        if(RR < *it && H[*it]+D <= H[RR]) ans++;
        else if(it != A.begin() && RR < *prev(it) && H[*prev(it)]+D <= H[RR]) ans++;
        else if(RR < R && H[R]+D <= H[RR]) ans++;
    } else if(RR < R && H[R]+D <= H[RR]) ans++;
    return ans;
}

• 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