Submission #1082138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082138		jer033	Radio Towers (IOI22_towers)	C++17	0 / 100	57 ms	40196 KiB

towers

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

vector<int> H;
int N;

class segTree{
public:
    int lef_ind;
    int rig_ind;
    int min_val;
    int max_val;
    segTree* lef_child;
    segTree* rig_child;
    
    segTree(int l, int r)
    {
        lef_ind = l;
        rig_ind = r;
        min_val = 500'000;
        max_val = -1;
        if (l!=r)
        {
            int mid = (l+r)/2;
            lef_child = new segTree(l, mid);
            rig_child = new segTree(mid+1, r);
        }
        else
        {
            lef_child = nullptr;
            rig_child = nullptr;
        }
    };

    void update(int ind, int val)
    {
        if (lef_child == nullptr)
        {
            min_val = min(min_val, val);
            max_val = max(max_val, val);
        }
        else
        {
            int mid = (lef_ind+rig_ind)/2;
            if (ind<=mid)
                lef_child->update(ind, val);
            else
                rig_child->update(ind, val);
            min_val = min(lef_child->min_val, rig_child->min_val);
            max_val = max(lef_child->max_val, rig_child->max_val);
        }
    }

    int mini(int l, int r)
    {
        int lef_overlap = max(l, lef_ind);
        int rig_overlap = min(r, rig_ind);
        if ((lef_ind==lef_overlap) and (rig_ind==rig_overlap))
            return min_val;
        if (lef_overlap < rig_overlap)
            return 500'000;
        return min(lef_child->mini(l, r), rig_child->mini(l, r));
    }

    int maxi(int l, int r)
    {
        int lef_overlap = max(l, lef_ind);
        int rig_overlap = min(r, rig_ind);
        if ((lef_ind==lef_overlap) and (rig_ind==rig_overlap))
            return max_val;
        if (lef_overlap < rig_overlap)
            return 0;
        return max(lef_child->maxi(l, r), rig_child->maxi(l, r));
    }
};

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

int max_towers(int L, int R, int D) {
    segTree lo = segTree(1, 100000);
    segTree hi = segTree(0, 100000);
    lo.update(1, H[L]);
    hi.update(0, H[L]);

    int ans = 1;

    for (int i=L+1; i<=R; i++)
    {
        //go high
        int bin_lo = 1;
        int bin_hi = i-L;//perhaps edit to 100'000?
        int target = H[i]-D;
        if (lo.mini(bin_lo, bin_hi) > target)
        {
            bin_lo = 0;
            bin_hi = 0;
        }
        while (bin_lo != bin_hi)
        {
            int bin_mid = (bin_lo + bin_hi + 1)/2;
            if (lo.mini(bin_mid, bin_hi) <= target)
                bin_lo = bin_mid;
            else
                bin_hi = bin_mid-1;
        }
        int ans_one = bin_lo;

        //go low
        bin_lo = 0;
        bin_hi = i-L;//perhaps edit to 100'000?
        target = H[i]+D;
        if (hi.maxi(bin_lo, bin_hi) < target)
        {
            bin_lo = 0;
            bin_hi = 0;
        }
        while (bin_lo != bin_hi)
        {
            int bin_mid = (bin_lo + bin_hi + 1)/2;
            if (hi.maxi(bin_mid, bin_hi) >= target)
                bin_lo = bin_mid;
            else
                bin_hi = bin_mid-1;
        }
        int ans_two = bin_lo+1;

        lo.update(ans_two, H[i]);
        hi.update(ans_one, H[i]);

        ans = max(ans, ans_two);
    }
    return ans;
}

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