oj.uz

Submission #633532

# Submission time Handle Problem Language Result Execution time Memory
633532 2022-08-22T17:01:22 Z JeanBombeur Radio Towers (IOI22_towers) C++17
15 / 100
 1016 ms 24152 KB 
#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;

vector <node_persistent> Tree;

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.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 < 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;
    Tree.resize(2 * SIZE, {-1, -1, 0});
    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 ++)
    {
        int root = MakeRoot();
        Remove(root, 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 9492 KB Output is correct
2 Correct 979 ms 11436 KB Output is correct
3 Correct 958 ms 11420 KB Output is correct
4 Correct 1012 ms 11472 KB Output is correct
5 Correct 1002 ms 11464 KB Output is correct
6 Correct 1016 ms 11472 KB Output is correct
7 Correct 980 ms 11424 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 4 ms 6480 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 6 ms 6480 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6480 KB Output is correct
11 Correct 3 ms 6480 KB Output is correct
12 Correct 3 ms 6480 KB Output is correct
13 Correct 3 ms 6480 KB Output is correct
14 Correct 3 ms 6480 KB Output is correct
15 Correct 4 ms 6480 KB Output is correct
16 Correct 5 ms 6480 KB Output is correct
17 Correct 4 ms 6480 KB Output is correct
18 Correct 3 ms 6480 KB Output is correct
19 Correct 4 ms 6488 KB Output is correct
20 Correct 3 ms 6480 KB Output is correct
21 Correct 4 ms 6480 KB Output is correct
22 Correct 4 ms 6480 KB Output is correct
23 Correct 3 ms 6480 KB Output is correct
24 Correct 3 ms 6480 KB Output is correct
25 Correct 3 ms 6480 KB Output is correct
26 Correct 4 ms 6480 KB Output is correct
27 Correct 3 ms 6464 KB Output is correct
28 Correct 4 ms 6608 KB Output is correct
29 Correct 4 ms 6480 KB Output is correct
30 Correct 4 ms 6480 KB Output is correct
31 Correct 4 ms 6480 KB Output is correct
32 Correct 5 ms 6480 KB Output is correct
33 Correct 5 ms 6480 KB Output is correct
34 Correct 4 ms 6480 KB Output is correct
35 Correct 4 ms 6480 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 6 ms 6480 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6480 KB Output is correct
11 Correct 3 ms 6480 KB Output is correct
12 Correct 3 ms 6480 KB Output is correct
13 Correct 3 ms 6480 KB Output is correct
14 Correct 3 ms 6480 KB Output is correct
15 Correct 4 ms 6480 KB Output is correct
16 Correct 5 ms 6480 KB Output is correct
17 Correct 4 ms 6480 KB Output is correct
18 Correct 3 ms 6480 KB Output is correct
19 Correct 4 ms 6488 KB Output is correct
20 Correct 3 ms 6480 KB Output is correct
21 Correct 4 ms 6480 KB Output is correct
22 Correct 4 ms 6480 KB Output is correct
23 Correct 3 ms 6480 KB Output is correct
24 Correct 3 ms 6480 KB Output is correct
25 Correct 3 ms 6480 KB Output is correct
26 Correct 4 ms 6480 KB Output is correct
27 Correct 3 ms 6464 KB Output is correct
28 Correct 4 ms 6608 KB Output is correct
29 Correct 4 ms 6480 KB Output is correct
30 Correct 4 ms 6480 KB Output is correct
31 Correct 4 ms 6480 KB Output is correct
32 Correct 5 ms 6480 KB Output is correct
33 Correct 5 ms 6480 KB Output is correct
34 Correct 4 ms 6480 KB Output is correct
35 Correct 4 ms 6480 KB Output is correct
36 Runtime error 39 ms 20416 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 24152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 7632 KB Output is correct
2 Runtime error 51 ms 24148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 4 ms 6480 KB Output is correct
3 Correct 6 ms 6480 KB Output is correct
4 Correct 4 ms 6480 KB Output is correct
5 Correct 4 ms 6480 KB Output is correct
6 Correct 4 ms 6480 KB Output is correct
7 Correct 4 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 3 ms 6480 KB Output is correct
11 Correct 3 ms 6480 KB Output is correct
12 Correct 3 ms 6480 KB Output is correct
13 Correct 3 ms 6480 KB Output is correct
14 Correct 3 ms 6480 KB Output is correct
15 Correct 4 ms 6480 KB Output is correct
16 Correct 5 ms 6480 KB Output is correct
17 Correct 4 ms 6480 KB Output is correct
18 Correct 3 ms 6480 KB Output is correct
19 Correct 4 ms 6488 KB Output is correct
20 Correct 3 ms 6480 KB Output is correct
21 Correct 4 ms 6480 KB Output is correct
22 Correct 4 ms 6480 KB Output is correct
23 Correct 3 ms 6480 KB Output is correct
24 Correct 3 ms 6480 KB Output is correct
25 Correct 3 ms 6480 KB Output is correct
26 Correct 4 ms 6480 KB Output is correct
27 Correct 3 ms 6464 KB Output is correct
28 Correct 4 ms 6608 KB Output is correct
29 Correct 4 ms 6480 KB Output is correct
30 Correct 4 ms 6480 KB Output is correct
31 Correct 4 ms 6480 KB Output is correct
32 Correct 5 ms 6480 KB Output is correct
33 Correct 5 ms 6480 KB Output is correct
34 Correct 4 ms 6480 KB Output is correct
35 Correct 4 ms 6480 KB Output is correct
36 Runtime error 39 ms 20416 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 9492 KB Output is correct
2 Correct 979 ms 11436 KB Output is correct
3 Correct 958 ms 11420 KB Output is correct
4 Correct 1012 ms 11472 KB Output is correct
5 Correct 1002 ms 11464 KB Output is correct
6 Correct 1016 ms 11472 KB Output is correct
7 Correct 980 ms 11424 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 3 ms 6480 KB Output is correct
10 Correct 4 ms 6480 KB Output is correct
11 Correct 3 ms 6480 KB Output is correct
12 Correct 4 ms 6480 KB Output is correct
13 Correct 6 ms 6480 KB Output is correct
14 Correct 4 ms 6480 KB Output is correct
15 Correct 4 ms 6480 KB Output is correct
16 Correct 4 ms 6480 KB Output is correct
17 Correct 4 ms 6480 KB Output is correct
18 Correct 3 ms 6480 KB Output is correct
19 Correct 3 ms 6480 KB Output is correct
20 Correct 3 ms 6480 KB Output is correct
21 Correct 3 ms 6480 KB Output is correct
22 Correct 3 ms 6480 KB Output is correct
23 Correct 3 ms 6480 KB Output is correct
24 Correct 3 ms 6480 KB Output is correct
25 Correct 4 ms 6480 KB Output is correct
26 Correct 5 ms 6480 KB Output is correct
27 Correct 4 ms 6480 KB Output is correct
28 Correct 3 ms 6480 KB Output is correct
29 Correct 4 ms 6488 KB Output is correct
30 Correct 3 ms 6480 KB Output is correct
31 Correct 4 ms 6480 KB Output is correct
32 Correct 4 ms 6480 KB Output is correct
33 Correct 3 ms 6480 KB Output is correct
34 Correct 3 ms 6480 KB Output is correct
35 Correct 3 ms 6480 KB Output is correct
36 Correct 4 ms 6480 KB Output is correct
37 Correct 3 ms 6464 KB Output is correct
38 Correct 4 ms 6608 KB Output is correct
39 Correct 4 ms 6480 KB Output is correct
40 Correct 4 ms 6480 KB Output is correct
41 Correct 4 ms 6480 KB Output is correct
42 Correct 5 ms 6480 KB Output is correct
43 Correct 5 ms 6480 KB Output is correct
44 Correct 4 ms 6480 KB Output is correct
45 Correct 4 ms 6480 KB Output is correct
46 Runtime error 39 ms 20416 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -