Submission #630200

#	Time	Username	Problem	Language	Result	Execution time	Memory
630200		qwerasdfzxcl	Radio Towers (IOI22_towers)	C++17	100 / 100	1367 ms	51488 KiB

towers

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

using namespace std;
typedef long long ll;
int n, a[100100], b[100100], typ[100100];
vector<int> T;

struct Node{
    int x, l, r;
    Node(){}
    Node(int _x, int _l, int _r): x(_x), l(_l), r(_r) {}
};
struct PST{
    Node tree[4004000];
    int root[100100], pt1, pt2, sz;
    void init(int n){
        sz = n;
        tree[0] = Node(0, -1, -1);
        root[0] = 0;
        pt1 = 1, pt2 = 1;
    }
    void add(){
        tree[pt1] = tree[root[pt2-1]];
        root[pt2] = pt1;
        ++pt1, ++pt2;
    }
    int _new(int i){
        if (i!=-1) tree[pt1++] = tree[i];
        else tree[pt1++] = Node(0, -1, -1);
        return pt1-1;
    }
    void build(int i, int l, int r, int a[]){
        if (l==r) {tree[i].x = a[l]; return;}
        int m = (l+r)>>1;

        tree[i].l = _new(tree[i].l);
        tree[i].r = _new(tree[i].r);
        build(tree[i].l, l, m, a); build(tree[i].r, m+1, r, a);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
    }
    void update(int i, int l, int r, int s, int x){
        if (r<s || s<l) return;
        if (l==r) {tree[i].x = x; return;}
        int m = (l+r)>>1;

        tree[i].l = _new(tree[i].l);
        tree[i].r = _new(tree[i].r);
        update(tree[i].l, l, m, s, x); update(tree[i].r, m+1, r, s, x);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
    }
    int query(int i, int l, int r, int s, int e){
        if (i==-1) return 0;
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }
    int left_bound(int i, int l, int r, int s, int e){
        if (r<s || e<l) return -1;
        if (tree[i].x==0) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = left_bound(tree[i].l, l, m, s, e);
        if (tmp!=-1) return tmp;
        return left_bound(tree[i].r, m+1, r, s, e);
    }
    int right_bound(int i, int l, int r, int s, int e){
        if (r<s || e<l) return -1;
        if (tree[i].x==0) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = right_bound(tree[i].r, m+1, r, s, e);
        if (tmp!=-1) return tmp;
        return right_bound(tree[i].l, l, m, s, e);
    }

    void update(int s, int x){
        update(root[pt2-1], 1, sz, s, x);
    }
    int query(int t, int l, int r){
        return query(root[t], 1, sz, l, r);
    }
    int left_bound(int t, int l, int r){
        return left_bound(root[t], 1, sz, l, r);
    }
    int right_bound(int t, int l, int r){
        return right_bound(root[t], 1, sz, l, r);
    }
}tree1;

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

set<int> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int myabs(int x){
    if (x<0) return -x;
    return x;
}

int getd(int x){
    auto iter = st.find(x);
    if (iter==st.end() || next(iter)==st.end()) return -1;
    return myabs(a[*next(iter)] - a[*iter]);
}

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

    int tl = 1, tr = n;
    for (;tl<n;tl++) if (a[tl] < a[tl+1]) break;
    for (;tr>1;tr--) if (a[tr-1] > a[tr]) break;
    assert(tl<=tr);

    st.insert(tl);
    st.insert(tr);
    b[tl] = b[tr] = 1;
    typ[tl] = typ[tr] = -1;
    for (int i=tl+1;i<tr;i++){
        if (a[i-1] < a[i] && a[i] > a[i+1]){
            b[i] = 1, typ[i] = 1;
            st.insert(i);
        }
        if (a[i-1] > a[i] && a[i] < a[i+1]){
            b[i] = 1, typ[i] = -1;
            st.insert(i);
        }
    }

    for (auto iter=st.begin();next(iter)!=st.end();iter++) pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);

    tree1.init(n);
    tree1.build(0, 1, n, b);
    tree2.init(n+1);
    T.push_back(0);

    while(!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if (getd(i)!=d) continue;

        auto iter = st.find(i);
        T.push_back(d);
        tree1.add();
        tree1.update(i, 0);
        tree1.update(*next(iter), 0);
        iter = st.erase(iter, next(next(iter)));

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

        if (iter==st.begin() || iter==st.end()) continue;
        //printf(" add: %d %d -> %d\n", *prev(iter), *iter, getd(*prev(iter)));
        --iter;
        pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);
    }

    /*for (int i=1;i<=n;i++) printf("%d ", b[i]);
    printf("\n");
    for (int i=1;i<=n;i++) printf("%d ", typ[i]);
    printf("\n");
    for (auto &x:T) printf("%d ", x);
    printf("\n");*/

    //printf("%d\n", tree1.tree[0].x);
}

int max_towers(int l, int r, int D) {
    ++l, ++r;
    int t = lower_bound(T.begin(), T.end(), D) - T.begin() - 1;
    int ans = tree1.query(t, l, r);
    //printf("%d -> ", ans);
    if (ans==0) return 1;

    int L = tree1.left_bound(t, l, r), R = tree1.right_bound(t, l, r);
    assert(L!=-1);
    assert(R!=-1);

    if (typ[L]==1){
        int tmp = tree2.query(l, L-1);
        if (a[L] - tmp >= D) ans++;
        else ans--;
    }
    if (ans==0) return 1;
    if (typ[R]==1){
        int tmp  = tree2.query(R+1, r);
        if (a[R] - tmp >= D) ans++;
        else ans--;
    }

    assert(ans%2==1);
    return (ans+1)/2;
}

• 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