oj.uz

Submission #762367

# Submission time Handle Problem Language Result Execution time Memory
762367 2023-06-21T10:47:35 Z doowey Radio Towers (IOI22_towers) C++17
0 / 100
 463 ms 8952 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 5548 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '119'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '119'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 463 ms 8952 KB 1st lines differ - on the 1st token, expected: '11903', found: '77656'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '119'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 5548 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -