Submission #633552

#	Time	Username	Problem	Language	Result	Execution time	Memory
633552		JeanBombeur	Radio Towers (IOI22_towers)	C++17	100 / 100	1274 ms	19608 KiB

towers

#include "towers.h"
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

//  <|°_°|>

//  M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int MAX_TOWERS = (1e5);
const int LOG = (17);
const int SIZE = (1 << LOG);

struct node_persistent {
    int left, right, sum;
};

struct node {
    int mini, maxi, id_maxi, delta_left, delta_right;
};

vector <pair <int, int>> Root;

node_persistent Tree[LOG * MAX_TOWERS];
int _size = 0;

node TreeOp[2 * MAX_TOWERS];

int Heights[MAX_TOWERS];

pair <int, int> Valleys[MAX_TOWERS];

int nbTowers;

node operator+(node a, node b) {
    return {min(a.mini, b.mini), max(a.maxi, b.maxi), Heights[a.id_maxi] > Heights[b.id_maxi] ? a.id_maxi : b.id_maxi, max(max(a.delta_left, b.delta_left), b.maxi - a.mini), max(max(a.delta_right, b.delta_right), a.maxi - b.mini)};
}

int Copy(int a, int &b) {
    Tree[_size ++] = Tree[a];
    return b = _size - 1;
}

int MakeRoot(int a = 1) {
    Root.push_back({0, Copy(Root.back().second, a)});
    return Root.back().second;
}

void Remove(int node, int target, int left = 0, int right = SIZE) {
    Tree[node].sum --;
    if (right - left == 1)
        return;
    int mid = (left + right) >> 1;
    if (target < mid)
        Remove(Copy(Tree[node].left, Tree[node].left), target, left, mid);
    else
        Remove(Copy(Tree[node].right, Tree[node].right), target, mid, right);
    return;
}

int GetSum(int node, int qleft, int qright, int left = 0, int right = SIZE) {
    if (left >= qright || right <= qleft)
        return 0;
    if (qleft <= left && right <= qright)
        return Tree[node].sum;
    int mid = (left + right) >> 1;
    return GetSum(Tree[node].left, qleft, qright, left, mid) + GetSum(Tree[node].right, qleft, qright, mid, right);
}

int GetPrev(int node, int target, int left = 0, int right = SIZE) {
    if (!Tree[node].sum)
        return -1;
    if (right - left == 1)
        return left;
    int mid = (left + right) >> 1;
    int ans = -1;
    if (target > mid)
        ans = GetPrev(Tree[node].right, target, mid, right);
    return ans < 0 ? GetPrev(Tree[node].left, target, left, mid) : ans;
}

int GetNext(int node, int target, int left = 0, int right = SIZE) {
    if (!Tree[node].sum)
        return -1;
    if (right - left == 1)
        return left;
    int mid = (left + right) >> 1;
    int ans = -1;
    if (target < mid)
        ans = GetNext(Tree[node].left, target, left, mid);
    return ans < 0 ? GetNext(Tree[node].right, target, mid, right) : ans;
}

node GetOp(int left, int right) {
    node ansLeft = {1LL << 30, 0, left, 0, 0};
    node ansRight = {1LL << 30, 0, left, 0, 0};
    for (left += nbTowers, right += nbTowers; left < right; left >>= 1, right >>= 1)
    {
        if (left & 1)
            ansLeft = ansLeft + TreeOp[left ++];
        if (right & 1)
            ansRight = TreeOp[-- right] + ansRight;
    }
    return ansLeft + ansRight;
}

int SearchLeft(int node, int target, int under) {
    if (under ? TreeOp[node].mini > target : TreeOp[node].maxi < target)
    {
        if (node == 1)
            return -1;
        if (~node & 1)
            return SearchLeft(-- node, target, under);
        return SearchLeft(node >> 1, target, under);
    }
    if (node >= nbTowers)
        return node - nbTowers;
    if (under ? TreeOp[2 * node + 1].mini > target : TreeOp[2 * node + 1].maxi < target)
        return SearchLeft(2 * node, target, under);
    return SearchLeft(2 * node + 1, target, under);
}

int SearchRight(int node, int target, int under) {
    if (under ? TreeOp[node].mini > target : TreeOp[node].maxi < target)
    {
        if (node == 1)
            return -1;
        if (node & 1)
            return SearchRight(++ node, target, under);
        return SearchRight(node >> 1, target, under);
    }
    if (node >= nbTowers)
        return node - nbTowers;
    if (under ? TreeOp[2 * node].mini > target : TreeOp[2 * node].maxi < target)
        return SearchRight(2 * node + 1, target, under);
    return SearchRight(2 * node, target, under);
}

void init(int N, vector <int> H) {
    nbTowers = N;
    _size = 2 * SIZE;
    int cnt = 0;
    for (int i = 0; i < nbTowers; i ++)
    {
        Heights[i] = H[i];
        TreeOp[i + nbTowers] = {Heights[i], Heights[i], i, 0, 0};
        if ((!i || H[i] < H[i - 1]) && (i + 1 == nbTowers || H[i] < H[i + 1]))
        {
            Tree[i + SIZE].sum = 1;
            Valleys[cnt ++].second = i;
        }
    }
    for (int i = SIZE - 1; i; i --)
    {
        Tree[i] = {2 * i, 2 * i + 1, Tree[2 * i].sum + Tree[2 * i + 1].sum};
    }
    for (int i = nbTowers - 1; i; i --)
    {
        TreeOp[i] = TreeOp[2 * i] + TreeOp[2 * i + 1];
    }
    for (int i = 0; i < cnt; i ++)
    {
        int id = Valleys[i].second;
        int left = GetOp(0, id).mini < Heights[id] ? SearchLeft(id + nbTowers, Heights[id] - 1, 1) : -1;
        int right = GetOp(id, nbTowers).mini < Heights[id] ? SearchRight(id + nbTowers, Heights[id] - 1, 1) : -1;
        left = left < 0 ? 1 << 30 : GetOp(left, id).maxi;
        right = right < 0 ? 1 << 30 : GetOp(id, right).maxi;
        Valleys[i].first = min(left, right) - Heights[id];
    }
    Root.push_back({0, 1});
    sort(Valleys, Valleys + cnt);
    for (int i = 0; i < cnt; i ++)
    {
        Remove(MakeRoot(), Valleys[i].second);
        Root.back().first = Valleys[i].first;
    }
    return;
}

int max_towers(int left, int right, int delta) {
    int root = 0;
    int sz = Root.size();
    for (int jump = SIZE; jump; jump >>= 1)
    {
        if (jump + root < sz && delta > Root[jump + root].first)
            root += jump;
    }
    root = Root[root].second;
    int ans = GetSum(root, left, ++ right);
    if (!ans)
    {
        int id = GetOp(left, right).id_maxi;
        if (max(GetOp(left, id).mini, GetOp(id, right).mini) + delta <= Heights[id])
            ans = 2;
        else
            ans = 1;
        return ans;
    }
    int next = GetNext(root, left), prev = GetPrev(root, right);
    ans += GetOp(left, next).maxi >= Heights[next] + delta && GetOp(left, SearchLeft(next + nbTowers, Heights[next] + delta, 0) + 1).delta_left >= delta;
    ans += GetOp(prev, right).maxi >= Heights[prev] + delta && GetOp(SearchRight(prev + nbTowers, Heights[prev] + delta, 0), right).delta_right >= delta;
    return 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