Submission #629868

#	Time	Username	Problem	Language	Result	Execution time	Memory
629868		spacewalker	Radio Towers (IOI22_towers)	C++17	23 / 100	4043 ms	20760 KiB

towers

#include "towers.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;
constexpr int INF = 1000000000;

vector<int> _heights;

void init(int N, std::vector<int> H) {
    _heights = H;
}

struct PakTree {
    int al, ar;
    int rmax;
    unique_ptr<PakTree> left, right;
    PakTree(int i, int j, vector<int> &pts) : al(pts[i]), ar(pts[j]), rmax(-INF) {
        if (i != j) {
            int k = (j - i) / 2 + i;
            left = make_unique<PakTree>(i, k, pts);
            right = make_unique<PakTree>(k+1, j, pts);
        }
    }
    void set(int i, int v) {
        if (i < al || ar < i) return;
        else if (left == nullptr) {
            rmax = v;
        } else {
            left->set(i, v); right->set(i, v);
            rmax = max(left->rmax, right->rmax);
        }
    }
    int getMax(int i, int j) {
        if (i <= al && ar <= j) return rmax;
        else if (ar < i || j < al) return -INF;
        else return max(left->getMax(i, j), right->getMax(i, j));
    }
    void _debug() {
        if (left == nullptr) {
            printf("(%d, %d) ", al, rmax);
        } else {
            left->_debug(); right->_debug();
        }
    }
    void debug(const char *label) {
        printf("%s: ", label);
        _debug();
        printf("\n");
    }
};

int max_towers(int L, int R, int D) {
    vector<int> heights(begin(_heights) + L, begin(_heights) + R + 1);
    vector<int> sheights = heights;
    int N = heights.size();
    sort(begin(sheights), end(sheights));
    PakTree lastUp(0, N - 1, sheights), lastDown(0, N - 1, sheights);
    for (int v : heights) {
        int ldPrev = lastDown.getMax(-INF, v - D);
        int luPrev = lastUp.getMax(v + D, INF);
        lastUp.set(v, ldPrev + 1);
        lastDown.set(v, max(luPrev + 1, 1)); // start is always a lastDown
        /*
        lastUp.debug("lastUp");
        lastDown.debug("lastDown");
        */
    }
    return lastDown.getMax(-INF, INF) / 2 + 1;
}

• 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