Submission #633425

#	Time	Username	Problem	Language	Result	Execution time	Memory
633425		JeanBombeur	Radio Towers (IOI22_towers)	C++17	0 / 100	429 ms	18612 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 {
    int left, right, sum;
};

vector <pair <int, int>> Root;

vector <node> Tree;

int TreeMax[2 * MAX_TOWERS];
int TreeMin[2 * MAX_TOWERS];

pair <int, int> Valleys[MAX_TOWERS];

int nbTowers;

int Copy(int a, int &b) {
    Tree.push_back(Tree[a]);
    return b = Tree.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 + 1 < mid)
        ans = GetNext(Tree[node].left, target, left, mid);
    return ans < 0 ? GetNext(Tree[node].right, target, mid, right) : ans;
}

int GetMax(int left, int right) {
    int ans = 0;
    for (left += nbTowers, right += nbTowers; left < right; left >>= 1, right >>= 1)
    {
        if (left & 1)
            ans = max(ans, TreeMax[left ++]);
        if (right & 1)
            ans = max(ans, TreeMax[-- right]);
    }
    return ans;
}

int Mini(int a, int b) {
    return TreeMax[a + nbTowers] < TreeMax[b + nbTowers] ? a : b;
}

int GetMin(int left, int right) {
    int ans = left;
    for (left += nbTowers, right += nbTowers; left < right; left >>= 1, right >>= 1)
    {
        if (left & 1)
            ans = Mini(ans, TreeMin[left ++]);
        if (right & 1)
            ans = Mini(ans, TreeMin[-- right]);
    }
    return ans;
}

void init(int N, vector <int> H) {
    nbTowers = N;
    Tree.resize(2 * SIZE, {-1, -1, 0});
    int cnt = 0;
    for (int i = 0; i < nbTowers; i ++)
    {
        TreeMax[i + nbTowers] = H[i];
        TreeMin[i + nbTowers] = i;
        if ((!i || H[i] < H[i - 1]) && (i + 1 == nbTowers || H[i] < H[i + 1]))
        {
            Tree[i + SIZE].sum = 1;
            Valleys[cnt ++] = {H[i], 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 --)
    {
        TreeMax[i] = max(TreeMax[2 * i], TreeMax[2 * i + 1]);
        TreeMin[i] = Mini(TreeMin[2 * i], TreeMin[2 * i + 1]);
    }
    Root.push_back({0, 1});
    sort(Valleys, Valleys + cnt);
    for (int i = cnt - 1; i; i --)
    {
        int id = Valleys[i].second;
        int root = MakeRoot();
        Remove(root, id);
        int left = GetPrev(root, id);
        int right = GetNext(root, id);
        left = left < 0 ? 1 << 30 : GetMax(left, id);
        right = right < 0 ? 1 << 30 : GetMax(id, right);
        Root.back().first = min(left, right) - TreeMax[id + nbTowers];
    }
    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)
        return 1;
    int next = GetNext(root, left - 1), prev = GetPrev(root, right);
    left = GetMin(left, next), right = GetMin(prev, right);
    ans += GetMax(left, next) - delta >= max(TreeMax[left + nbTowers], TreeMax[next + nbTowers]);
    ans += GetMax(prev, right) - delta >= max(TreeMax[prev + nbTowers], TreeMax[right - nbTowers]);
    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