Submission #1073079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073079		Zicrus	Radio Towers (IOI22_towers)	C++17	23 / 100	4078 ms	5580 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;
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);
    }
}

int max_towers(int L, int R, int D) {
    if (!initialized) init2(D);
    
    int res = 0;
    bool foundK = false;
    int cur = L;
    while (cur <= R) {
        res++;
        cur = segPeak[pow2+cur];
        cur = segVal[pow2+cur];
    }
    return res;
}

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

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:122:10: warning: unused variable 'foundK' [-Wunused-variable]
  122 |     bool foundK = false;
      |          ^~~~~~

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