Submission #635155

#	Time	Username	Problem	Language	Result	Execution time	Memory
635155		phathnv	Radio Towers (IOI22_towers)	C++17	0 / 100	101 ms	44972 KiB

towers

#include "towers.h"

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

struct Node {
    int nLeft;
    int nRight;
    int l, r, sum, minPos, maxPos, minVal;
    Node(){};
    Node(int _l, int _r, int val) {
        nLeft = nRight = -1;
        l = _l;
        r = _r;
        sum = 0;
        minPos = 1e9;
        maxPos = -1e9;
        minVal = val;
        assert(l <= r);
    }
};

int cntNode;
Node nodes[2000000];

int newNode(int l, int r, int val) {
    int id = cntNode;
    nodes[id] = Node(l, r, val);
    ++cntNode;
    return id;
}

int mergeNode(int a, int b) {
    assert(nodes[a].r + 1 == nodes[b].l);
    int res = newNode(nodes[a].l, nodes[b].r, 1e9);
    nodes[res].nLeft = a;
    nodes[res].nRight = b;
    nodes[res].sum = nodes[a].sum + nodes[b].sum;
    nodes[res].minPos = min(nodes[a].minPos, nodes[b].minPos);
    nodes[res].maxPos = max(nodes[a].maxPos, nodes[b].maxPos);
    nodes[res].minVal = min(nodes[a].minVal, nodes[a].minVal);
    return res;
}

int build(int l, int r, const vector<int>& h, const vector<bool>& mark) {
    if (l == r) {
        int n = newNode(l, r, h[l]);
        if (mark[l]) {
            nodes[n].sum = 1;
            nodes[n].minPos = nodes[n].maxPos = l;
        }
        return n;
    }
    int mid = (l + r) >> 1;
    return mergeNode(build(l, mid, h, mark), build(mid + 1, r, h, mark));
}

int update(int n, int pos) {
    assert(n != -1);
    if (pos < nodes[n].l || nodes[n].r < pos) {
        return n;
    }
    if (nodes[n].l == nodes[n].r) {
        assert(nodes[n].sum == 1);
        return newNode(nodes[n].l, nodes[n].r, nodes[n].minVal);
    }
    return mergeNode(update(nodes[n].nLeft, pos), update(nodes[n].nRight, pos));
}

int getMin(int n, int l, int r) {
    assert(n != -1);
    if (r < nodes[n].l || nodes[n].r < l) {
        return 1e9;
    }
    if (l <= nodes[n].l && nodes[n].r <= r) {
        return nodes[n].minVal;
    }
    return min(getMin(nodes[n].nLeft, l, r), getMin(nodes[n].nRight, l, r));
}

void get(int n, int l, int r, int &x, int &y, int &sum) {
    if (r < nodes[n].l || nodes[n].r < l) {
        return;
    }
    if (l <= nodes[n].l && nodes[n].r <= r) {
        sum += nodes[n].sum;
        x = min(x, nodes[n].minPos);
        y = max(y, nodes[n].maxPos);
        return;
    }
    get(nodes[n].nLeft, l, r, x, y, sum);
    get(nodes[n].nRight, l, r, x, y, sum);
}

int n;
vector<int> h;
vector<int> type, changingPoint;
vector<int> roots;

void init(int _n, vector<int> _h) {
    n = _n;
    h = _h;

    set<int> s;
    s.insert(0);
    for (int i = 1; i < n; ++i) {
        if (s.size() & 1) {
            if (h[i] > h[*s.rbegin()]) {
                s.insert(i);
            } else {
                s.erase(*s.rbegin());
                s.insert(i);
            }
        } else {
            if (h[i] < h[*s.rbegin()]) {
                s.insert(i);
            } else {
                s.erase(*s.rbegin());
                s.insert(i);
            }
        }
    }
    if (s.size() % 2 == 0) {
        s.erase(*s.rbegin());
    }

    //for (auto x : s) {
        //cerr << x << ' ';
    //}
    //cerr << endl;

    vector<bool> mark(n, false);
    for (auto x : s) {
        mark[x] = true;
    }
    changingPoint.push_back(0);
    roots.push_back(build(0, n - 1, h, mark));

    priority_queue<array<int, 3>> pq;
    type.assign(n, -1);
    int pre = -1, t = 0;
    for (int cur : s) {
        type[cur] = t;
        t ^= 1;
        if (pre != -1) {
            pq.push({-abs(h[pre] - h[cur]), pre, cur});
        }
        pre = cur;
    }

    int last = 0;
    while (!pq.empty()) {
        auto [d, l, r] = pq.top();
        pq.pop();
        if (!mark[l] || !mark[r]) {
            continue;
        }

        d = -d;
        if (d != last) {
            changingPoint.push_back(d);
            roots.push_back(roots.back());
            last = d;
        }

        int a[5] = {-1, -1, -1, -1, -1};

        if (h[l] > h[r]) {
            a[1] = l;
            a[2] = r;
            auto it = s.lower_bound(l);
            if (it != s.begin()) {
                a[0] = *(--it);
            }
            it = s.lower_bound(r);
            ++it;
            if (it != s.end()) {
                a[3] = *it;
                ++it;
            }
            if (it != s.end()) {
                a[4] = *it;
                ++it;
            }
        } else {
            a[2] = l;
            a[3] = r;
            auto it = s.lower_bound(l);
            if (it != s.begin()) {
                a[1] = *(--it);
            }
            if (it != s.begin()) {
                a[0] = *(--it);
            }
            it = s.lower_bound(r);
            ++it;
            if (it != s.end()) {
                a[4] = *it;
                ++it;
            }
        }

        roots.back() = update(roots.back(), a[2]);
        mark[a[2]] = false;
        s.erase(a[2]);
        if (h[a[1]] == -1 || h[a[3]] == -1) {
            if (mark[a[1]]) {
                roots.back() = update(roots.back(), a[1]);
                mark[a[1]] = false;
                s.erase(a[1]);
            }
            if (mark[a[3]]) {
                roots.back() = update(roots.back(), a[3]);
                mark[a[3]] = false;
                s.erase(a[3]);
            }
        } else {
            if (h[a[1]] > h[a[3]]) {
                roots.back() = update(roots.back(), a[3]);
                mark[a[3]] = false;
                s.erase(a[3]);
                pq.push({-abs(h[a[1]] - h[a[4]]), a[1], a[4]});
            } else {
                roots.back() = update(roots.back(), a[1]);
                mark[a[1]] = false;
                s.erase(a[1]);
                pq.push({-abs(h[a[0]] - h[a[3]]), a[0], a[3]});
            }
        }

        //cerr << "change " << d << ' ' << l << ' ' << r << endl;
        for (int i = 0; i < 5; ++i) {
            //cerr << a[i] << ' ';
        }
        //cerr << endl;
    }
}

int max_towers(int l, int r, int d) {
    int root = roots[lower_bound(changingPoint.begin(), changingPoint.end(), d) - changingPoint.begin() - 1];

    int x = 1e9, y = -1e9, res = 0;
    get(root, l, r, x, y, res);

    if (x > y) {
        return 1;
    }

    assert(type[x] != -1 && type[y] != -1);

    if (type[x] == 1) {
        if (h[x] - d >= getMin(root, l, x - 1)) {
            ++res;
        } else {
            --res;
        }
    }
    if (type[y] == 1) {
        if (h[y] - d >= getMin(root, y + 1, r)) {
            ++res;
        } else {
            --res;
        }
    }

    //cerr << "query " << l << ' ' << r << ' ' << d << ' ' << res << endl;
    return max(1, (res + 1) / 2);
}

• 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