Submission #689729

#	Time	Username	Problem	Language	Result	Execution time	Memory
689729		lohacho	Radio Towers (IOI22_towers)	C++17	0 / 100	945 ms	39544 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, spa2, spa3;
vector<int> lp, rp;
vector<int> mn;

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));
    spa2.resize(n, vector<int>(20, (int)1e9));
    spa3.resize(n, vector<int>(20, (int)1e9));
    lp.resize(n);
    rp.resize(n);
    mn.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][0] = i + rp[i];
            for(int j = 1; j < 20; ++j){
                if(spa[i][j - 1] < n - 1){
                    spa[i][j] = spa2[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]);
                }
                for(int j = 0; j < 20; ++j){
                    spa2[i][j] = min(spa2[i][j], spa2[i + 1][j]);
                }
            }
            for(int j = 0; j < 20; ++j){
                spa2[i - lp[i]][j] = min(spa2[i - lp[i]][j], spa[i][j]);
            }

            mn[i - lp[i]] = min(mn[i - lp[i]], i);
        }

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

    int ans = 0;
    int pos = L, f = 1;
    for(int i = 19; i >= 0; --i){
        if(f){
            if(spa[pos][i] <= R){
                ans += (1 << i);
                pos = spa[pos][i] + 1;
            }
            f = 0;
        }
        else{
            if(spa2[pos][i] <= R){
                ans += (1 << i);
                pos = spa2[pos][i] + 1;
            }
        }
    }
    if(!ans) ans = 1;
    else{
        if(pos <= R){
            if(mn[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