제출 #762367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762367		doowey	Radio Towers (IOI22_towers)	C++17	0 / 100	463 ms	8952 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;
const int LOG = 17;
int L[N], R[N];
int tab[LOG][N];
int G[N];
int n;

int get_max(int l, int r){
    int sz = (r - l + 1);
    return max(tab[G[sz]][l], tab[G[sz]][r - (1 << G[sz]) + 1]);
}

vector<int> lis;

void init(int _n, vector<int> H) {
    n = _n;
    for(int i = 0 ; i < n; i ++ ) L[i] = R[i] = -1;
    vector<int> ord;
    for(int i = 0 ; i < n; i ++ ){
        tab[0][i] = H[i];
        // ------------------
        while(!ord.empty() && H[ord.back()] > H[i]){
            R[ord.back()] = i;
            ord.pop_back();
        }
        if(!ord.empty()){
            L[i] = ord.back();
        }
        ord.push_back(i);
    }
    for(int ln = 1; ln < LOG; ln ++ ){
        for(int i = 0 ; i < n; i ++){
            if((i + (1 << ln) - 1) < n){
                tab[ln][i] = max(tab[ln - 1][i], tab[ln - 1][i + (1 << (ln - 1))]);
            }
        }
    }
    int lg = 0;
    for(int sz = 1; sz <= n; sz ++ ){
        while((1 << (lg + 1)) <= sz){
            lg ++ ;
        }
        G[sz] = lg;
    }
    int maxi;
    int need;
    for(int i = 0; i < n; i ++ ){
        need = (int)1e9;
        if(L[i] != -1){
            need = min(need, get_max(L[i],i)-H[i]);
        }
        if(R[i] != -1){
            need = min(need, get_max(i,R[i])-H[i]);
        }
        lis.push_back(need);
    }

}
int max_towers(int L, int R, int delta) {
    int id = lower_bound(lis.begin(), lis.end(), delta) - lis.begin();
    return (int)lis.size() - id;
}

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

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:57:9: warning: unused variable 'maxi' [-Wunused-variable]
   57 |     int maxi;
      |         ^~~~

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