Submission #733261

#	Time	Username	Problem	Language	Result	Execution time	Memory
733261		puppy	Radio Towers (IOI22_towers)	C++17	23 / 100	4089 ms	5424 KiB

towers

#include "towers.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
namespace {
    int N, K;
    int H[100005];
}

void init(int N, std::vector<int> H) {
    ::N = N;
    ::K = -1;
    for (int i = 0; i < N; i++) {
        ::H[i] = H[i];
    }
}
int dp[100005];
struct maxseg
{
    vector<int> tree;
    maxseg(int n)
    {
        int sz = 1 << ((int)ceil(log2(n))+1);
        tree.resize(sz);
    }
    int init(int s, int e, int node, vector<int> &vc)
    {
        if (s == e) return tree[node] = vc[s];
        else return tree[node] = max(init(s, (s+e)/2, 2*node, vc), init((s+e)/2+1, e, 2*node+1, vc));
    }
    void upd(int s, int e, int node, int id, int val)
    {
        if (e < id || id < s) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        upd(s, (s+e)/2, 2*node, id, val);
        upd((s+e)/2+1, e, 2*node+1, id, val);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
    int query(int s, int e, int node, int l, int r)
    {
        if (e < l || r < s) return 0;
        if (l <= s && e <= r) return tree[node];
        return max(query(s, (s+e)/2, 2*node, l, r), query((s+e)/2+1, e, 2*node+1, l, r));
    }
};
int max_towers(int L, int R, int D) {
    int M = R - L + 1;
    vector<int> A(M);
    for (int i = L; i <= R; i++) A[i - L] = H[i];
    maxseg seg(M), seg2(M);
    seg.init(0, M-1, 1, A);
    dp[0] = 1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(A[0], 0));
    for (int i = 1; i < M; i++) {
        //키가 A[i] - D 이하인 애들을 모두 해방시키자
        while (!pq.empty() && pq.top().first <= A[i] - D) {
            seg2.upd(0, M-1, 1, pq.top().second, dp[pq.top().second]);
            pq.pop();
        }
        int l = 0, r = i - 1; //max(k ... i) >= A[i] + D인 최대 k 찾기
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (seg.query(0, M-1, 1, m, i) >= A[i] + D) {
                l = m;
            }
            else r = m - 1;
        }
        if (seg.query(0, M-1, 1, l, i) < A[i] + D) l = -1;
        dp[i] = seg2.query(0, M-1, 1, 0, l) + 1;
        pq.push(make_pair(A[i], i));
    }
    int ans = 0;
    for (int i = 0; i < M; i++) ans = max(ans, dp[i]);
    return ans;
    //0부터 M-1까지 A에서 문제 풀기
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:70:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int m = l + r + 1 >> 1;
      |                     ~~~~~~^~~

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