Submission #628858

#	Time	Username	Problem	Language	Result	Execution time	Memory
628858		qwerasdfzxcl	Radio Towers (IOI22_towers)	C++17	17 / 100	927 ms	12816 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, a[100100], mn[100100];
priority_queue<int> pq[100100];
vector<int> G;

struct Seg{
    pair<int, int> tree[200200];
    int sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    pair<int, int> query(int l, int r){
        ++r;
        pair<int, int> ret = {-1, 0};
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(ret, tree[--r]);
        }
        return ret;
    }
}tree;

void merge(int x, int l, int r, int d){
    if (pq[l].size() < pq[r].size()) swap(l, r);
    pq[l].push(d);
    while(!pq[r].empty()){
        pq[l].push(pq[r].top());
        pq[r].pop();
    }

    swap(pq[x], pq[l]);
}

int dnc(int l, int r){
    if (l>r) return -1;
    if (l==r) {mn[l] = a[l]; return l;}
    auto [mx, mid] = tree.query(l, r);

    int L = dnc(l, mid-1), R = dnc(mid+1, r);

    if (L==-1){
        swap(pq[mid], pq[R]);
        mn[mid] = mn[R];
    }
    else if (R==-1){
        swap(pq[mid], pq[L]);
        mn[mid] = mn[L];
    }
    else{
        mn[mid] = min(mn[L], mn[R]);
        merge(mid, L, R, mx-max(mn[L], mn[R]));
    }

    //printf("%d %d -> %d / %d\n", l, r, mid, mn[mid]);

    return mid;
}

void init(int N, std::vector<int> H) {
    n = N;
    for (int i=1;i<=n;i++) a[i] = H[i-1];
    tree.init(n+1);

    int tmp = dnc(1, n);
    while(!pq[tmp].empty()){
        G.push_back(pq[tmp].top()); pq[tmp].pop();
    }
    reverse(G.begin(), G.end());

    //for (auto &x:G) printf("%d ", x);
    //printf("\n");
}

int max_towers(int l, int r, int D) {
    ++l, ++r;
    int sz = G.size();
    return sz - (lower_bound(G.begin(), G.end(), D) - G.begin()) + 1;
}

• 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