제출 #762371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762371		doowey	송신탑 (IOI22_towers)	C++17	11 / 100	4062 ms	10648 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 H[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;
        H[i] = _H[i];
    }
    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 solve(int l, int r, int delta, int bound){
    if(l>r) return 0;
    int big = l;
    bool emp = true;
    for(int i = l ; i <= r; i ++ ){
        if(H[i] > H[big]) big = i;
        if(H[i] <= bound){
            emp = false;
        }
    }
    if(emp) return 0;
    return max(1, solve(l,big-1,delta,H[big]-delta)+solve(big+1,r,delta,H[big]-delta));
}


int max_towers(int L, int R, int delta) {
    //int id = lower_bound(lis.begin(), lis.end(), delta) - lis.begin();
    //int sol1 = (int)lis.size() - id;
    int sol2 = solve(L, R, delta, (int)1e9 + 1);
    //cout << sol1 << " " << sol2 << "\n";
    return sol2;
}

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

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

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