Submission #689733

#	Time	Username	Problem	Language	Result	Execution time	Memory
689733		lohacho	Radio Towers (IOI22_towers)	C++17	0 / 100	1321 ms	31272 KiB

towers

#include "towers.h"

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

int n;
vector<int> a;
vector<int> leaf, lt;
vector<vector<int>> spa;
vector<int> lp, rp;
vector<int> mnl, mnr;

struct fenw{
    int n;
    vector<int> tr;

    fenw(int m){
        n = m + 4;
        tr.resize(n, -1);
    }

    void push(int pos, int val){
        for(int i = pos; i < n; i += (i & -i)){
            tr[i] = max(tr[i], val);
        }
    }

    int get(int pos){
        int rv = -1;

        for(int i = pos; i > 0; i -= (i & -i)){
            rv = max(rv, tr[i]);
        }

        return rv;
    }
};

int fir = 0;

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

    spa.resize(n, vector<int>(20, (int)1e9));
    lp.resize(n);
    rp.resize(n);
    mnr.resize(n, (int)1e9);
    mnl.resize(n, (int)1e9);
}

int max_towers(int L, int R, int D) {
    if(!fir){
        fir = 1;
        vector<int> srt;
        for(int i = 0; i < n; ++i){
            srt.push_back(a[i]);
            srt.push_back(a[i] + D);
        }

        sort(srt.begin(), srt.end());
        srt.erase(unique(srt.begin(), srt.end()), srt.end());

        auto getnum = [&](int x)->int{
            return lower_bound(srt.begin(), srt.end(), x) - srt.begin();
        };

        auto getl = [&](vector<int> x)->vector<int>{
            fenw tr((int)srt.size() + 4);
            vector<int> rv(n);

            for(int i = 0; i < n; ++i){
                rv[i] = tr.get((int)srt.size() - getnum(a[i] + D)) + 1;
                rv[i] = i - rv[i];
                tr.push((int)srt.size() - getnum(a[i]), i);
            }

            return rv;
        };

        lp = getl(a);
        reverse(a.begin(), a.end());
        rp = getl(a);
        reverse(a.begin(), a.end());
        reverse(rp.begin(), rp.end());

        // for(int i = 0; i < n; ++i){
        //     cout << i - lp[i] << ' ' << i + rp[i] << endl;
        // }
        // cout << endl;

        for(int i = n - 1; i >= 0; --i){
            spa[i - lp[i]][0] = min(spa[i - lp[i]][0], i + rp[i]);
            for(int j = 1; j < 20; ++j){
                if(spa[i][j - 1] < n - 1){
                    spa[i][j] = spa[spa[i][j - 1] + 1][j - 1];
                }
            }
            if(i + 1 < n){
                for(int j = 0; j < 20; ++j){
                    spa[i][j] = min(spa[i][j], spa[i + 1][j]);
                }
            }

            mnl[i - lp[i]] = min(mnl[i - lp[i]], i);
            mnr[i] = i + rp[i];
        }

        for(int i = n - 2; i >= 0; --i){
            mnl[i] = min(mnl[i], mnl[i + 1]);
            mnr[i] = min(mnr[i], mnr[i + 1]);
        }
    }

    int ans = 1;
    int pos = mnr[L] + 1;
    for(int i = 19; i >= 0; --i){
        if(spa[pos][i] < R){
            ans += (1 << i);
            pos = spa[pos][i] + 1;
        }
    }
    if(mnl[pos] <= R){
        ++ans;
    }

    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