제출 #705612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705612		danikoynov	송신탑 (IOI22_towers)	C++17	58 / 100	4035 ms	16268 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];

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 > 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]);
        ///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 ++;
    if (L == 1 && R == n)
    {
        int ans = val.size();
        int lf = 0, rf = (int)(val.size()) - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (val[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;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |     for (int i = 0; i < n; i ++)
      |     ^~~
towers.cpp:86:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |         for (int i = 1; i <= n; i ++)
      |         ^~~
towers.cpp:118:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  118 |         while(!st.empty() && h[st.back()] >= h[i])
      |         ^~~~~
towers.cpp:120:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  120 |             aft[i] = st.back();
      |             ^~~
towers.cpp:135:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  135 |     if (aft[i] == n + 1)
      |     ^~
towers.cpp:137:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  137 |         val.push_back(min(h1, h2) - h[i]);
      |         ^~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23