Submission #1079478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079478		ProtonDecay314	Radio Towers (IOI22_towers)	C++17	28 / 100	1432 ms	85468 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--)

/*
DTree (DiffTree)

Computes the largest forward difference within a range

Formally, max l <= i <= j <= r of h[j] - h[i]
*/
struct DTreeState {
    int mn, mx, difff, diffb;

    DTreeState operator+(const DTreeState& o) const {
        if(mn == 0) return o;
        else if(o.mn == 0) return {mn, mx, difff, diffb};
        return {min(mn, o.mn), max(mx, o.mx), max(difff, o.mx - mn), max(diffb, mx - o.mn)};
    }
};

class DTree {
    public:
        int l, r;
        DTree *lt, *rt;
        DTreeState v;

        DTree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), v({0, 0, 0}) {}

        void combine() {
            v = lt->v + rt->v; // ! Careful! Addition is noncommutative!
        }

        void build(const vi& a) {
            if(l == r) {
                v = {a[l], a[l], 0, 0};

                return;
            }

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

            lt = new DTree(l, m);

            rt = new DTree(m + 1, r);

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

            combine();
        }

        DTreeState qry(int ql, int qr) {
            if(ql > r || qr < l) return {0, 0, 0, 0};

            if(ql == l && qr == r) {
                return v;
            }

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

            return lt->qry(ql, min(qr, m)) + rt->qry(max(ql, m + 1) , qr);
        }
};

/*
LTree (Lease Tree)

The lease tree will compute the maximum and minimum indices to be leased
if the value of delta is D

Notice that each node has a corresponding max delta and index

Now, what if we store the deltas in increasing order? (could be decreasing too)

Then, when the value of delta is D, that means that a suffix (or prefix) would
be the values in consideration

Well, now, what if we compute the min and max indices over a prefix?

So it reduces to binary search ^^

It reduces to two binary searches, actually, so Q log^2 N per query

Conceptually, a node would have a schema of...

type Node = {
    l, r: int
    lt, rt: Node*
    deltas: [delta, ind][]
    mins: int[]
    maxs: int[]
}
*/
class LTree {
    public:
        int l, r;
        LTree *lt, *rt;
        vpi deltas;
        vi mins;
        vi maxs;

        LTree(int a_l, int a_r): l(a_l), r(a_r), deltas(), mins(), maxs() {}
        
        void combine() {
            int lds = lt->deltas.size(), rds = rt->deltas.size();

            int ldp = 0, rdp = 0;

            while(ldp < lds && rdp < rds) {
                if(lt->deltas[ldp].fi > rt->deltas[rdp].fi) {
                    deltas.pb(lt->deltas[ldp]);
                    ldp++;
                } else {
                    deltas.pb(rt->deltas[rdp]);
                    rdp++;
                }
            }

            while(ldp < lds) {
                deltas.pb(lt->deltas[ldp]);
                ldp++;
            }

            while(rdp < rds) {
                deltas.pb(rt->deltas[rdp]);
                rdp++;
            }

            int ds = deltas.size();

            mins.reserve(ds);
            maxs.reserve(ds);

            mins.pb(INF(int));
            maxs.pb(NINF(int));

            for(int i = 0; i < ds; i++) {
                mins.pb(min(mins.back(), deltas[i].se));
                maxs.pb(max(maxs.back(), deltas[i].se));
            }
        }

        void build(const vi& d) {
            if(l == r) {
                deltas.pb({d[l], l});
                mins.pb(INF(int));
                mins.pb(l);
                maxs.pb(NINF(int));
                maxs.pb(l);
                return;
            }

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

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

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

            combine();
        }

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

            if(ql == l && qr == r) {
                int ds = deltas.size();
                int li = -1, ri = ds;

                while(ri - li > 1) {
                    int m = (li + ri) >> 1;

                    if(deltas[m].fi >= d) li = m;
                    else ri = m;
                }

                return {mins[li + 1], maxs[li + 1]};
            }

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

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

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

        int qry_count(int ql, int qr, int d) {
            if(ql > r || qr < l) return 0;

            if(ql == l && qr == r) {
                int ds = deltas.size();
                int li = -1, ri = ds;

                while(ri - li > 1) {
                    int m = (li + ri) >> 1;

                    if(deltas[m].fi >= d) li = m;
                    else ri = m;
                }

                return li + 1;
            }

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

            return lt->qry_count(ql, min(qr, m), d) + rt->qry_count(max(m + 1, ql), qr, d);
        }
};

int n;
vi h;

DTree* dtr;
LTree* ltr;
vi dvals;

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

    // Create DTree
    dtr = new DTree(0, n - 1);

    dtr->build(h);

    // Compute critical d-values
    for(int i = 0; i < n; i++) {
        int l1 = -1, r1 = i;

        while(r1 - l1 > 1) {
            int m = (l1 + r1) >> 1;

            if(dtr->qry(m, i).mn < h[i]) l1 = m;
            else r1 = m;
        }

        int l2 = i, r2 = n;

        while(r2 - l2 > 1) {
            int m = (l2 + r2) >> 1;

            if(dtr->qry(i, m).mn < h[i]) r2 = m;
            else l2 = m;
        }
        
        int min_h = INF(int);

        if(l1 != -1) {
            min_h = min(min_h, dtr->qry(l1, i).mx);
        }

        if(r2 != n) {
            min_h = min(min_h, dtr->qry(i, r2).mx);
        }

        dvals.pb(min_h - h[i]);
    }

    ltr = new LTree(0, n - 1);
    ltr->build(dvals);
}

int max_towers(int L, int R, int D) {
    auto [li, ri] = ltr->qry(L, R, D);
    // cout << "! " << li << " " << ri << endl;
    int ans = 0;

    if(li == INF(int)) {
        // Case 1 (wow, research follows me everywhere): no leased in the range
        // Check forward and backward largest diffs

        auto state = dtr->qry(L, R);

        if(state.diffb >= D) ans++;
        if(state.difff >= D) ans++;
    } else {
        // Case 2 (res reference???): there is at least one leased in the range
        ans = ltr->qry_count(L, R, D);

        if(dtr->qry(L, li - 1).difff >= D) ans++;
        if(dtr->qry(ri + 1, R).diffb >= D) ans++;
    }

    return max(ans, 1);
}

/*
Last frontier
kodoku na hoshitachi e sasageru uta wo
Last moment
hitori de saihate e tabidatsu uta wo
Last of all
majiwaru koto no nai sekai wo
ima kaeru kara saigo ni
kimi to boku wa deau
*/

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