oj.uz

Submission #705647

# Submission time Handle Problem Language Result Execution time Memory
705647 2023-03-04T22:37:16 Z danikoynov Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 7500 KB 
#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];

int tree[4 * maxn];

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = h[left];
        return;
    }

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

    tree[root] = max(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] = max(tree[root * 2], tree[root * 2 + 1]);
}

int 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 max(query(root * 2, left, mid, qleft, qright),
               query(root * 2 + 1, mid + 1, right, qleft, qright));
}

vector < pair < int, int > > val;
void init(int N, std::vector<int> H)
{
    n = N;
    for (int i = 0; i < n; i ++)
        h[i + 1] = H[i];

    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);
    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);
        if (bef[i] == 0)
            h1 = 2e9 + 10;
        if (aft[i] != i + 1)
            h2 = query(1, 1, n, i + 1, aft[i] - 1);
        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());
    //for (int v : val)
    //    cout << v << " ";
    // cout << endl;
}


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

    L ++;
    R ++;


    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;
    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);
        }
    }


    if (leftmost > rightmost)
    {
        return 1;
    }

    int highest_tower = 0;
    ///cout << leftmost << " " << rightmost << endl;
    for (int tower = leftmost - 1; tower >= L; tower --)
    {
        if (h[tower] + D <= highest_tower &&
            highest_tower >= h[leftmost] + D)
        {
            ans ++;
            break;
        }
            highest_tower = max(highest_tower, h[tower]);
    }

    highest_tower = 0;
    for (int tower = rightmost + 1; tower <= R; tower ++)
    {
        if (h[tower] + D <= highest_tower &&
            highest_tower >= h[rightmost] + D)
        {
            ans ++;
            break;
        }
         highest_tower = max(highest_tower, h[tower]);
    }

    return ans;



}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:167:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = lf; i < val.size(); i ++)
      |                      ~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 5328 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2768 KB Output is correct
9 Correct 2 ms 2768 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Incorrect 1 ms 2640 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2768 KB Output is correct
9 Correct 2 ms 2768 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Incorrect 1 ms 2640 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4049 ms 7248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 3792 KB Output is correct
2 Correct 2958 ms 7120 KB Output is correct
3 Correct 2678 ms 7116 KB Output is correct
4 Correct 3883 ms 7168 KB Output is correct
5 Correct 3868 ms 7116 KB Output is correct
6 Correct 3834 ms 7116 KB Output is correct
7 Correct 3844 ms 7104 KB Output is correct
8 Execution timed out 4094 ms 7500 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2768 KB Output is correct
9 Correct 2 ms 2768 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Incorrect 1 ms 2640 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 5328 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -