Submission #1079227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079227		ProtonDecay314	Radio Towers (IOI22_towers)	C++17	23 / 100	4077 ms	1082996 KiB

towers

// AM + DG
#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

class Tree {
    public:
        int l, r;
        Tree *lt, *rt;
        int mnv, mxv;

        Tree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mnv(NINF(int)), mxv(INF(int)) {};

        void combine() {
            mnv = min(lt->mnv, rt->mnv);
            mxv = max(lt->mxv, rt->mxv);
        }

        void build(const vi& a) {
            if(l == r) {
                mnv = mxv = a[l];

                return;
            }

            int m = (l + r) >> 1;

            lt = new Tree(l, m);
            rt = new Tree(m + 1, r);

            lt->build(a);
            rt->build(a);

            combine();
        }

        pi qry(int ql, int qr) {
            if(ql > r || qr < l) return {INF(int), NINF(int)};

            if(ql == l && qr == r) return {mnv, mxv};

            int m = (l + r) >> 1;

            auto [mn1, mx1] = lt->qry(ql, min(qr, m));
            auto [mn2, mx2] = rt->qry(max(ql, m + 1), qr);

            return {min(mn1, mn2), max(mx1, mx2)};
        }
};

int n;
vi h_glob;

void init(int N, vi H) {
    n = N;
    h_glob = H;
}

int solve(vi h, int n, int d) {
    Tree tr(0, n - 1);
    tr.build(h);

    vpi num;

    for(int i = 0; i < n; i++) {
        num.pb({i, h[i]});
    }

    sort(num.begin(), num.end(), [](pi p1, pi p2) {return p1.se < p2.se;});

    // I'm pretty sure you can use ordered set, but I'm not Walsh :P
    // but yes, pwede ordered set HAHA
    set<pi> s;

    int ans = 1;

    s.insert(num[0]);

    for(int i = 1; i < n; i++) {
        int li = -1;
        int ri = -1;

        int cur_i = num[i].fi;
        int cur_v = num[i].se;

        auto cur_it = s.lower_bound({cur_i, cur_v});

        if(cur_it != s.begin()) {
            // There is a previous element!
            li = prev(cur_it)->fi;
        }

        if(cur_it != s.end()) {
            ri = cur_it->fi;
        }

        if((li == -1 || tr.qry(li, cur_i).se >= cur_v + d) && (ri == -1 || tr.qry(cur_i, ri).se >= cur_v + d)) {
            ans++;
        }

        s.insert({cur_i, cur_v});
    }

    return ans;
}

int max_towers(int L, int R, int D) {
    vi cut;

    for(int i = L; i <= R; i++) {
        cut.pb(h_glob[i]);
    }

    return solve(cut, cut.size(), D);
}

/*
The last frontier
*/

• 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