Submission #1073108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073108		Zicrus	Radio Towers (IOI22_towers)	C++17	56 / 100	838 ms	17092 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;

typedef long long ll;

int n, pow2;
vector<int> h;
vector<int> segMn, segMx, segPeak, segVal;
vector<vector<int>> jmp;
bool initialized;

int nxtPeak(int i, int val) {
    i += pow2;
    while (i) {
        if (segMx[i] >= val) break;
        if (i & 1) {
            if ((i & (i+1)) == 0) return n;
            i++;
        }
        i /= 2;
    }
    while (i < pow2) {
        if (segMx[2*i] >= val) i = 2*i;
        else i = 2*i+1;
    }
    return i-pow2;
}

int nxtVal(int i, int val) {
    i += pow2;
    while (i) {
        if (segMn[i] <= val) break;
        if (i & 1) {
            if ((i & (i+1)) == 0) return n;
            i++;
        }
        i /= 2;
    }
    while (i < pow2) {
        if (segMn[2*i] <= val) i = 2*i;
        else i = 2*i+1;
    }
    return i-pow2;
}

void setSegPeak(int i, int val) {
    i += pow2;
    segPeak[i] = val;
    i /= 2;
    while (i) {
        segPeak[i] = min(segPeak[2*i], segPeak[2*i+1]);
        i /= 2;
    }
}

void setSegVal(int i, int val) {
    i += pow2;
    segVal[i] = val;
    i /= 2;
    while (i) {
        segVal[i] = min(segVal[2*i], segVal[2*i+1]);
        i /= 2;
    }
}

int getSegPeak(int low, int high) {
    low += pow2; high += pow2;
    int res = n;
    while (low <= high) {
        if (low & 1) res = min(res, segPeak[low++]);
        if (!(high & 1)) res = min(res, segPeak[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

int getSegVal(int low, int high) {
    low += pow2; high += pow2;
    int res = n;
    while (low <= high) {
        if (low & 1) res = min(res, segVal[low++]);
        if (!(high & 1)) res = min(res, segVal[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

void init(int N, vector<int> H) {
    n = N; h = H;
    initialized = false;
    pow2 = 1 << (int)ceil(log2(n));
    segMn = vector<int>(2*pow2);
    segMx = vector<int>(2*pow2);
    for (int i = 0; i < n; i++) {
        segMn[pow2+i] = h[i];
        segMx[pow2+i] = h[i];
    }
    for (int i = pow2-1; i > 0; i--) {
        segMn[i] = min(segMn[2*i], segMn[2*i+1]);
        segMx[i] = max(segMx[2*i], segMx[2*i+1]);
    }
}

void init2(int D) {
    initialized = true;
    segPeak = vector<int>(2*pow2, n);
    segVal = vector<int>(2*pow2, n);
    for (int i = n-2; i >= 0; i--) {
        int nxtP = nxtPeak(i+1, h[i]+D);
        int nxtV = nxtVal(i+1, h[i]-D);
        nxtP = min(nxtP, getSegPeak(i+1, nxtP-1));
        nxtV = min(nxtV, getSegVal(i+1, nxtV-1));
        setSegPeak(i, nxtP);
        setSegVal(i, nxtV);
    }
    jmp = vector<vector<int>>(n, vector<int>(20, n));
    for (int i = 0; i < n; i++) {
        jmp[i][0] = segVal[pow2+segPeak[pow2+i]];
    }
    for (int b = 1; b < 20; b++) {
        for (int i = 0; i < n; i++) {
            int nxt = jmp[i][b-1];
            if (nxt >= n) continue;
            jmp[i][b] = jmp[nxt][b-1];
        }
    }
}

int max_towers(int L, int R, int D) {
    if (!initialized) init2(D);
    
    int res = 1;
    int cur = L;
    for (int b = 20-1; b >= 0; b--) {
        int nxt = jmp[cur][b];
        if (nxt > R) continue;
        cur = nxt;
        res += 1 << b;
    }
    return res;
}

#ifdef TEST
#include "stub.cpp"
#endif

• 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