Submission #761502

#	Time	Username	Problem	Language	Result	Execution time	Memory
761502		doowey	Radio Towers (IOI22_towers)	C++17	56 / 100	4098 ms	13912 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 h[N];
int tab[LOG][N];
int n;


void init(int _n, vector<int> H) {
    n = _n;
    for(int i = 0 ; i < n; i ++ ){
        h[i] = H[i];
        tab[0][i] = h[i];
    }
    for(int ln = 1; ln < LOG; ln ++ ){
        for(int i = 0 ; i + (1 << ln) - 1 < n; i ++ ){
            tab[ln][i] = min(tab[ln-1][i], tab[ln-1][i + (1 << (ln - 1))]);
        }
    }
}

int D = -1;
int jump[LOG][N];

void compute_diff(int dd){
    if(D != dd){
        D = dd;
        for(int i = 0 ; i <= n; i ++ ){
            jump[0][i] = n;
        }
        int lf, rf;
        for(int c = 1; c + 1 < n; c ++ ){
            lf = c;
            rf = c;
            for(int ln = LOG - 1; ln >= 0 ; ln -- ){
                if(lf - (1 << ln) >= 0 && tab[ln][lf - (1 << ln)] > h[c] - dd){
                    lf -= (1 << ln);
                }
                if(rf + (1 << ln) < n && tab[ln][rf + 1] > h[c] - dd){
                    rf += (1 << ln);
                }
            }
            lf -- ;
            rf ++ ;
            if(lf < 0) continue;
            jump[0][lf] = min(jump[0][lf], rf);
        }
        for(int i = n - 1; i >= 0; i -- ){
            jump[0][i]=min(jump[0][i],jump[0][i+1]);
        }
        for(int l = 1; l < LOG; l ++ ){
            for(int i = 0 ; i <= n; i ++ ){
                jump[l][i]=jump[l-1][jump[l-1][i]];
            }
        }
    }
}
int max_towers(int L, int R, int delta) {
    compute_diff(delta);
    int res = 1;
    for(int ln = LOG - 1; ln >= 0 ; ln -- ){
        if(jump[ln][L] <= R){
            L=jump[ln][L];
            res += (1 << ln);
        }
    }
    return res;
}

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