Submission #705674

#	Time	Username	Problem	Language	Result	Execution time	Memory
705674		danikoynov	Radio Towers (IOI22_towers)	C++17	100 / 100	1517 ms	43068 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, h[maxn], pref[maxn], peak_pos;
int cnt = 0;


int par[maxn], rnk[maxn];

int find_leader(int v)
{
    return (v == par[v]) ? v : par[v] = find_leader(par[v]);
}

void unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return;

    if (rnk[v] < rnk[u])
        swap(v, u);
    rnk[v] += rnk[u];
    par[u] = v;
}

int dp[maxn], bef[maxn], aft[maxn];


struct node
{
    int max_number, min_number;

    node(int _max_number = 0, int _min_number = 2e9)
    {
        max_number = _max_number;
        min_number = _min_number;
    }
};

node tree[4 * maxn];
node merge_node(node left, node right)
{
    node comb;
    comb.max_number = max(left.max_number, right.max_number);
    comb.min_number = min(left.min_number, right.min_number);
    return comb;
}
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = node(h[left], h[left]);
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int pos, int val)
{
    if (left == right)
    {
        tree[root] = val;
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        update(root * 2, left, mid, pos, val);
    else
        update(root * 2 + 1, mid + 1, right, pos, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return 0;

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query(root * 2, left, mid, qleft, qright),
                      query(root * 2 + 1, mid + 1, right, qleft, qright));
}

int find_rightmost(int root, int left, int right, int qleft, int qright, int val)
{
    ///cout << root << " " << left << " " << right << " " << qleft << " " << qright << " " << val << endl;
    if (tree[root].max_number < val ||
            left > qright || right < qleft)
        return 0;

    if (left == right)
        return left;

    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2 + 1].max_number >= val)
            return find_rightmost(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return find_rightmost(root * 2, left, mid, qleft, qright, val);
    }

    return max(find_rightmost(root * 2, left, mid, qleft, qright, val),
               find_rightmost(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int find_leftmost(int root, int left, int right, int qleft, int qright, int val)
{
    if (tree[root].max_number < val ||
            left > qright || right < qleft)
        return n + 1;

    if (left == right)
        return left;
    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2].max_number >= val)
            return find_leftmost(root * 2, left, mid, qleft, qright, val);
        return find_leftmost(root * 2 + 1, mid + 1, right, qleft, qright, val);

    }

    return min(find_leftmost(root * 2, left, mid, qleft, qright, val),
               find_leftmost(root * 2 + 1, mid + 1, right, qleft, qright, val));
}



struct diff_node
{
    int max_number, min_number;
    int diff_to_right;
    int diff_to_left;

    diff_node()
    {
        max_number = 0;
        min_number = 2e9;
        diff_to_right = 0;
        diff_to_left = 0;
    }
};

diff_node merge_diff(diff_node dn1, diff_node dn2)
{
    diff_node res;
    res.max_number = max(dn1.max_number, dn2.max_number);
    res.min_number = min(dn1.min_number, dn2.min_number);
    res.diff_to_right = max(dn2.max_number - dn1.min_number, max(dn1.diff_to_right, dn2.diff_to_right));
    res.diff_to_left = max(dn1.max_number - dn2.min_number, max(dn1.diff_to_left, dn2.diff_to_left));
    return res;
}

diff_node diff_tree[4 * maxn];
void build_diff_tree(int root, int left, int right)
{
    if (left == right)
    {
        diff_tree[root].max_number = diff_tree[root].min_number = h[left];
        return;
    }

    int mid = (left + right) / 2;
    build_diff_tree(root * 2, left, mid);
    build_diff_tree(root * 2 + 1, mid + 1, right);

    diff_tree[root] = merge_diff(diff_tree[root * 2], diff_tree[root * 2 + 1]);
}

diff_node diff_query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return diff_node();

    if (left >= qleft && right <= qright)
        return diff_tree[root];

    int mid = (left + right) / 2;
    return merge_diff(diff_query(root * 2, left, mid, qleft, qright),
                      diff_query(root * 2 + 1, mid + 1, right, qleft, qright));
}

vector < pair < int, int > > val;
unordered_map < int, int > rev;
vector < int > merge_tree[4 * maxn];

void conquer(int left_root, int right_root, int root)
{
    int idx1 = 0, idx2 = 0;
    while(idx1 < merge_tree[left_root].size() && idx2 < merge_tree[right_root].size())
    {
        if (merge_tree[left_root][idx1] < merge_tree[right_root][idx2])
        {
            merge_tree[root].push_back(merge_tree[left_root][idx1 ++]);
        }
        else
        {
            merge_tree[root].push_back(merge_tree[right_root][idx2 ++]);
        }
    }

    while(idx1 < merge_tree[left_root].size())
                    merge_tree[root].push_back(merge_tree[left_root][idx1 ++]);

    while(idx2 < merge_tree[right_root].size())
                    merge_tree[root].push_back(merge_tree[right_root][idx2 ++]);
}

void divide(int root, int left, int right)
{
    if (left == right)
    {
        merge_tree[root].push_back(val[left].second);
        return;
    }

    int mid = (left + right) / 2;
    divide(root * 2, left, mid);
    divide(root * 2 + 1, mid + 1, right);

    conquer(root * 2, root * 2 + 1, root);
}

int query_max_under_node(int root, int val)
{
    int lf = 0, rf = (int)(merge_tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (merge_tree[root][mf] <= val)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    if (rf < 0)
        return 0;
    return merge_tree[root][rf];
}

int query_min_above_node(int root, int val)
{
    int lf = 0, rf = (int)(merge_tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (merge_tree[root][mf] >= val)
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    if (lf == merge_tree[root].size())
        return n + 1;
    return merge_tree[root][lf];
}

int query_min_above(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft)
        return n + 1;

    if (left >= qleft && right <= qright)
        return query_min_above_node(root, val);

    int mid = (left + right) / 2;
    return min(query_min_above(root * 2, left, mid, qleft, qright, val),
               query_min_above(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int query_max_under(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft)
        return 0;

    if (left >= qleft && right <= qright)
        return query_max_under_node(root, val);

    int mid = (left + right) / 2;
    return max(query_max_under(root * 2, left, mid, qleft, qright, val),
               query_max_under(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

int query_between_node(int root, int min_val, int max_val)
{
    int lf = 0, rf = (int)(merge_tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (merge_tree[root][mf] <= max_val)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    int rb = rf;

        lf = 0;
         rf = (int)(merge_tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (merge_tree[root][mf] >= min_val)
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    int lb = lf;

    return (rb - lb + 1);

}

int query_between(int root, int left, int right, int qleft, int qright, int min_val, int max_val)
{
    if (left > qright || right < qleft)
        return 0;

    if (left >= qleft && right <= qright)
        return query_between_node(root, min_val, max_val);

    int mid = (left + right) / 2;
    return query_between(root * 2, left, mid, qleft, qright, min_val, max_val) +
            query_between(root * 2 + 1, mid + 1, right, qleft, qright, min_val, max_val);
}
void init(int N, std::vector<int> H)
{
    n = N;
    for (int i = 0; i < n; i ++)
        h[i + 1] = H[i], rev[H[i]] = i + 1;

    for (int i = 1; i <= n; i ++)
        if (h[i] > h[i - 1] && h[i] > h[i + 1])
            cnt ++;
    for (int i = 2; i < n; i ++)
    {
        pref[i] = pref[i - 1];
        if (h[i] > h[i - 1] && h[i] > h[i + 1])
        {
            pref[i] ++, peak_pos = i;

        }
    }

    build_tree(1, 1, n);
    build_diff_tree(1, 1, n);
    vector < int > st;
    st.push_back(0);
    for (int i = 1; i <= n; i ++)
    {


        while(!st.empty() && h[st.back()] >= h[i])
            st.pop_back();
        bef[i] = st.back();
        st.push_back(i);
    }

    st.clear();
    st.push_back(n + 1);
    for (int i = n; i > 0; i --)
    {


        while(!st.empty() && h[st.back()] >= h[i])
            st.pop_back();
        aft[i] = st.back();
        st.push_back(i);
    }

    for (int i = 1; i <= n; i ++)
    {

        ///cout << bef[i] << " " << aft[i] << endl;
        int h1 = 0, h2 = 0;
        if (bef[i] != i - 1)
            h1 = query(1, 1, n, bef[i] + 1, i - 1).max_number;
        if (bef[i] == 0)
            h1 = 2e9 + 10;
        if (aft[i] != i + 1)
            h2 = query(1, 1, n, i + 1, aft[i] - 1).max_number;
        if (aft[i] == n + 1)
            h2 = 2e9 + 10;
        val.push_back({min(h1, h2) - h[i], i});
        ///cout << query(1, 1, n, bef[i] + 1)
    }

    sort(val.begin(), val.end());

    divide(1, 0, val.size() - 1);
    //for (int v : val)
    //    cout << v << " ";
    // cout << endl;
}


vector < int > act[maxn];
int cnt_query = 0;
int max_towers(int L, int R, int D)
{

    L ++;
    R ++;
    cnt_query ++;


    int lf = 0, rf = (int)(val.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (val[mf].first < D)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    ///vector < int > towers;
    int leftmost = n + 1, rightmost = 0, ans = 0;
    rightmost = query_max_under(1, 0, val.size() - 1, lf, val.size() - 1, R);
    leftmost = query_min_above(1, 0, val.size() - 1, lf, val.size() - 1, L);
    ans = query_between(1, 0, val.size() - 1, lf, val.size() - 1, L, R);
    /**for (int i = lf; i < val.size(); i ++)
    {
        if (val[i].second >= L && val[i].second <= R)
        {
            ///ans ++;
            ///towers.push_back(val[i].second);
            ///leftmost = min(leftmost, val[i].second);
            ///rightmost = max(rightmost, val[i].second);
        }
    }*/
    ///cout << leftmost << " " << rightmost << endl;

    if (leftmost > rightmost)
    {
        int lowest_tower = rev[query(1, 1, n, L, R).min_number];
        leftmost = lowest_tower;
        rightmost = lowest_tower;
        ans = 1;
    }

    int highest_tower = 0;
    int La = find_rightmost(1, 1, n, 1, leftmost, h[leftmost] + D);
    diff_node dn = diff_query(1, 1, n, L, La);
    if (dn.diff_to_right >= D)
        ans ++;
    ///cout << La << endl;
    ///cout << leftmost << " " << rightmost << endl;
    /**for (int tower = leftmost - 1; tower >= L; tower --)
    {
        if (tower <= La && h[tower] + D <= highest_tower &&
                highest_tower >= h[leftmost] + D)
        {
            ans ++;
            break;
        }
        highest_tower = max(highest_tower, h[tower]);
    }*/

    highest_tower = 0;
    int Ra = find_leftmost(1, 1, n, rightmost, n, h[rightmost] + D);
    dn = diff_query(1, 1, n, Ra, R);
    if (dn.diff_to_left >= D)
        ans ++;
    /**for (int tower = rightmost + 1; tower <= R; tower ++)
    {

        if (tower >= Ra && h[tower] + D <= highest_tower &&
                highest_tower >= h[rightmost] + D)
        {
            ans ++;
            break;
        }
        highest_tower = max(highest_tower, h[tower]);
    }*/

    return ans;



}

Compilation message (stderr)

towers.cpp: In function 'void conquer(int, int, int)':
towers.cpp:203:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     while(idx1 < merge_tree[left_root].size() && idx2 < merge_tree[right_root].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:203:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     while(idx1 < merge_tree[left_root].size() && idx2 < merge_tree[right_root].size())
      |                                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:215:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     while(idx1 < merge_tree[left_root].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:218:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     while(idx2 < merge_tree[right_root].size())
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int query_min_above_node(int, int)':
towers.cpp:265:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |     if (lf == merge_tree[root].size())
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:453:9: warning: variable 'highest_tower' set but not used [-Wunused-but-set-variable]
  453 |     int highest_tower = 0;
      |         ^~~~~~~~~~~~~

• 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