oj.uz

Submission #705603

# Submission time Handle Problem Language Result Execution time Memory
705603 2023-03-04T18:50:11 Z danikoynov Radio Towers (IOI22_towers) C++17
4 / 100
 893 ms 5996 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 < int > peaks, val, block;
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;
            peaks.push_back(i);
        }
    }

    build_tree(1, 1, n);
    int last = 0;
    for (int i = 0; i < peaks.size(); i ++)
    {

        val.push_back(query(1, 1, n, last + 1, peaks[i] - 1));
        ///cout << val.back() << " ";
        last = peaks[i];
    }

    val.push_back(query(1, 1, n, last + 1, n));
    ///cout << val.back() << " ";
    ///cout << endl;
    for (int i = 0; i < peaks.size(); i ++)
    {
        block.push_back(h[peaks[i]] - max(val[i], val[i + 1]));
        ///cout << block.back() << endl;
    }
    sort(block.begin(), block.end());
}


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

    L ++;
    R ++;
    if (L == 1 && R == n)
    {
        int ans = val.size();
        int lf = 0, rf = (int)(block.size()) - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (block[mf] < D)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        return ans - lf;
    }

    if (cnt == 1)
    {
        if (peak_pos <= L || peak_pos >= R)
            return 1;
        if (h[L] <= h[peak_pos] - D && h[R] <= h[peak_pos] - D)
            return 2;
        return 1;
    }
    if (D == 1)
    {
        int peaks = max(0, pref[R - 1] - pref[L]);
        return peaks + 1;
    }
    for (int i = 0; i < n; i ++)
        act[i].clear();
    for (int i = 0; i < 4 * n; i ++)
        tree[i] = 0;
    h[0] = h[n + 1] = 2e9;
    vector < int > st;
    st.push_back(0);
    for (int i = 1; i <= n; i ++)
    {
        int lf = 0, rf = st.size() - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (h[st[mf]] - D >= h[i])
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        bef[i] = st[rf];

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

    st.clear();
    st.push_back(n + 1);
    for (int i = n; i > 0; i --)
    {
        int lf = 0, rf = st.size() - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (h[st[mf]] - D >= h[i])
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        aft[i] = st[rf];

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

    int ans = 0;
    for (int i = L; i <= R; i ++)
    {
        for (int pos : act[i])
        {
            update(1, 0, n - 1, pos, dp[pos]);
        }
        act[i].clear();

        dp[i] = 1;
        int left = L, right = bef[i];
        if (left <= right)
        {
            int x = query(1, 0, n - 1, left, right) + 1;
            dp[i] = x;
        }

        act[aft[i]].push_back(i);

        ans = max(ans, dp[i]);
    }

    return ans;
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:82:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   82 |     for (int i = 0; i < n; i ++)
      |     ^~~
towers.cpp:85:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |         for (int i = 1; i <= n; i ++)
      |         ^~~
towers.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < peaks.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
towers.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < peaks.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 4048 KB Output is correct
2 Correct 681 ms 5332 KB Output is correct
3 Correct 608 ms 5212 KB Output is correct
4 Correct 773 ms 5212 KB Output is correct
5 Correct 789 ms 5192 KB Output is correct
6 Correct 873 ms 5228 KB Output is correct
7 Correct 786 ms 5224 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2768 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 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2640 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 3 ms 2640 KB Output is correct
18 Correct 3 ms 2640 KB Output is correct
19 Correct 1 ms 2640 KB Output is correct
20 Incorrect 2 ms 2640 KB 1st lines differ - on the 1st token, expected: '670', found: '560'
21 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2768 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 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2640 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 3 ms 2640 KB Output is correct
18 Correct 3 ms 2640 KB Output is correct
19 Correct 1 ms 2640 KB Output is correct
20 Incorrect 2 ms 2640 KB 1st lines differ - on the 1st token, expected: '670', found: '560'
21 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 5888 KB Output is correct
2 Correct 754 ms 5808 KB Output is correct
3 Correct 893 ms 5840 KB Output is correct
4 Correct 650 ms 5964 KB Output is correct
5 Correct 757 ms 5996 KB Output is correct
6 Correct 828 ms 5972 KB Output is correct
7 Correct 837 ms 5976 KB Output is correct
8 Correct 883 ms 5200 KB Output is correct
9 Correct 709 ms 5204 KB Output is correct
10 Correct 820 ms 5328 KB Output is correct
11 Correct 474 ms 5212 KB Output is correct
12 Correct 697 ms 5208 KB Output is correct
13 Correct 798 ms 5236 KB Output is correct
14 Correct 1 ms 2640 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 20 ms 5852 KB Output is correct
18 Correct 23 ms 5960 KB Output is correct
19 Correct 24 ms 5984 KB Output is correct
20 Correct 12 ms 5192 KB Output is correct
21 Correct 13 ms 5192 KB Output is correct
22 Incorrect 20 ms 5836 KB 1st lines differ - on the 1st token, expected: '33289', found: '27837'
23 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 3420 KB 1st lines differ - on the 1st token, expected: '7197', found: '4514'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2768 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 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2768 KB Output is correct
11 Correct 2 ms 2768 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 2 ms 2640 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 3 ms 2640 KB Output is correct
18 Correct 3 ms 2640 KB Output is correct
19 Correct 1 ms 2640 KB Output is correct
20 Incorrect 2 ms 2640 KB 1st lines differ - on the 1st token, expected: '670', found: '560'
21 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 4048 KB Output is correct
2 Correct 681 ms 5332 KB Output is correct
3 Correct 608 ms 5212 KB Output is correct
4 Correct 773 ms 5212 KB Output is correct
5 Correct 789 ms 5192 KB Output is correct
6 Correct 873 ms 5228 KB Output is correct
7 Correct 786 ms 5224 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 1 ms 2640 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct
13 Correct 2 ms 2768 KB Output is correct
14 Correct 2 ms 2768 KB Output is correct
15 Correct 2 ms 2768 KB Output is correct
16 Correct 2 ms 2768 KB Output is correct
17 Correct 2 ms 2768 KB Output is correct
18 Correct 2 ms 2640 KB Output is correct
19 Correct 2 ms 2640 KB Output is correct
20 Correct 2 ms 2768 KB Output is correct
21 Correct 2 ms 2768 KB Output is correct
22 Correct 2 ms 2640 KB Output is correct
23 Correct 2 ms 2640 KB Output is correct
24 Correct 2 ms 2640 KB Output is correct
25 Correct 2 ms 2640 KB Output is correct
26 Correct 2 ms 2640 KB Output is correct
27 Correct 3 ms 2640 KB Output is correct
28 Correct 3 ms 2640 KB Output is correct
29 Correct 1 ms 2640 KB Output is correct
30 Incorrect 2 ms 2640 KB 1st lines differ - on the 1st token, expected: '670', found: '560'
31 Halted 0 ms 0 KB -