Submission #771496

#	Time	Username	Problem	Language	Result	Execution time	Memory
771496		PurpleCrayon	Radio Towers (IOI22_towers)	C++17	100 / 100	1739 ms	172524 KiB

towers

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
const int L = 20;

struct D1 {
    int sum, mn, mx;

    D1() {
        sum = 0;
        mn = MOD;
        mx = -1;
    }

    D1(int x, int loc) {
        sum = x;
        if (x) mn = mx = loc;
        else mn = MOD, mx = -1;
    }

    friend D1 operator + (const D1& one, const D1& two) {
        D1 ans;
        ans.sum = one.sum + two.sum;
        ans.mn = min(one.mn, two.mn);
        ans.mx = max(one.mx, two.mx);
        return ans;
    }
};

struct T1 {
    D1 d;
    T1 *l, *r;

    T1(D1 _d): d(_d) {
        l = nullptr;
        r = nullptr;
    }

    T1(T1* _l, T1* _r): l(_l), r(_r) {
        d = l->d + r->d;
    }
};

T1* build1(int tl, int tr, const vector<int>& v) {
    if (tl == tr) {
        return new T1(D1(v[tl], tl));
    }
    else {
        int tm = (tl + tr) / 2;
        T1* ans = new T1(build1(tl, tm, v), build1(tm+1, tr, v));
        return ans;
    }
}

T1* upd1(T1* t, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        return new T1(D1(x, tl));
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new T1(upd1(t->l, tl, tm, pos, x), t->r);
    else
        return new T1(t->l, upd1(t->r, tm+1, tr, pos, x));
}

D1 qry1(T1* t, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return D1();
    if (l <= tl && tr <= r) return t->d;
    int tm = (tl + tr) / 2;
    return qry1(t->l, tl, tm, l, r) + qry1(t->r, tm+1, tr, l, r);
}

struct D2 {
    int mn, left_big, right_big, mx_active;

    D2() {
        mn = MOD;
        left_big = right_big = -1;
        mx_active = -MOD;
    }

    D2(int x, bool active) {
        mn = x;
        left_big = right_big = -1;
        if (active) mx_active = x;
        else mx_active = -MOD;
    }

    friend D2 operator + (const D2& one, const D2& two) {
        D2 res;
        res.mn = min(one.mn, two.mn);
        res.mx_active = max(one.mx_active, two.mx_active);
        res.right_big = max({one.right_big, two.right_big, two.mx_active - one.mn});
        res.left_big = max({one.left_big, two.left_big, one.mx_active - two.mn});
        return res;
    }
};

struct T2 {
    D2 d;
    T2 *l, *r;

    T2(D2 _d): d(_d) {
        l = nullptr;
        r = nullptr;
    }

    T2(T2* _l, T2* _r): l(_l), r(_r) {
        d = l->d + r->d;
    }
};

T2* build2(int tl, int tr, const vector<int>& v) {
    if (tl == tr) {
        return new T2(D2(v[tl], false));
    }
    else {
        int tm = (tl + tr) / 2;
        T2* ans = new T2(build2(tl, tm, v), build2(tm+1, tr, v));
        return ans;
    }
}

T2* upd2(T2* t, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        return new T2(D2(x, true));
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new T2(upd2(t->l, tl, tm, pos, x), t->r);
    else
        return new T2(t->l, upd2(t->r, tm+1, tr, pos, x));
}

D2 qry2(T2* t, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return D2();
    if (l <= tl && tr <= r) return t->d;
    int tm = (tl + tr) / 2;
    return qry2(t->l, tl, tm, l, r) + qry2(t->r, tm+1, tr, l, r);
}


int n, a[N], st[N][L];
vector<pair<int, int>> store;
vector<int> base;
vector<int> ord;
T1* vers[N];
ar<int, 2> st_min[N][L];

pair<int, int> sorted[N];
T2* vers2[N];

void build_rmq() {
    for (int i = 0; i < n; i++) st[i][0] = a[i];
    for (int k = 2, l = 1; k <= n; k *= 2, l++) {
        for (int i = 0; i + k <= n; i++) {
            st[i][l] = max(st[i][l-1], st[i + k / 2][l-1]);
        }
    }

    for (int i = 0; i < n; i++) st_min[i][0] = {a[i], i};
    for (int k = 2, l = 1; k <= n; k *= 2, l++) {
        for (int i = 0; i + k <= n; i++) {
            st_min[i][l] = min(st_min[i][l-1], st_min[i + k / 2][l-1]);
        }
    }
}

int qry_max(int l, int r) {
    int len = r - l + 1;
    int use = 31 - __builtin_clz(len);
    return max(st[l][use], st[r - (1 << use) + 1][use]);
}

ar<int, 2> qry_min(int l, int r) {
    int len = r - l + 1;
    int use = 31 - __builtin_clz(len);
    return min(st_min[l][use], st_min[r - (1 << use) + 1][use]);
}

void init(int _n, vector<int> H) {
    n = _n;
    for (int i = 0; i < n; i++) {
        a[i] = H[i];
    }
    build_rmq();

    set<int> s;
    for (int i = 0; i < n; i++) {
        bool use = 1;
        if (i && a[i-1] < a[i]) use = 0;
        if (i < n-1 && a[i+1] < a[i]) use = 0;
        if (use) s.insert(i);
    }
    base = vector<int>(s.begin(), s.end());

    auto f = [&](int i) {
        auto it = s.lower_bound(i); assert(*it == i);
        --it;
        return qry_max(*it, i) - max(a[*it], a[i]);
    };

    set<pair<int, int>> q;
    auto get_v = [&](int x) {
        return pair<int, int>{f(x), x};
    };

    for (auto it = next(s.begin()); it != s.end(); it++) {
        q.insert(get_v(*it));
    }

    vector<pair<int, int>> v;
    v.emplace_back(0, sz(s)); // d > 0, ans = sz(s)
    while (sz(q)) {
        auto [d, i] = *q.begin(); q.erase(q.begin());
        v.emplace_back(d, -1); // need to update v.back().second

        auto it = s.lower_bound(i); assert(*it == i);
        int one = i;
        int two = *prev(it);
        if (next(it) != s.end()) {
            q.erase(get_v(*next(it)));
        }

        if (prev(it) != s.begin()) {
            q.erase(get_v(two));
        }

        if (a[one] > a[two]) {
            s.erase(one);
            ord.push_back(one);
            it = s.lower_bound(two);
            if (next(it) != s.end()) {
                q.insert(get_v(*next(it)));
            }
            if (it != s.begin()) {
                q.insert(get_v(*it));
            }
        } else {
            s.erase(two);
            ord.push_back(two);
            it = s.lower_bound(one);
            if (next(it) != s.end()) {
                q.insert(get_v(*next(it)));
            }
            if (it != s.begin()) {
                q.insert(get_v(*it));
            }
        }

        v.back().second = sz(s);
    }

    store.push_back(v[0]);
    for (int i = 1; i < sz(v); i++) {
        if (v[i].first <= store.back().first) {
            store.back().second = v[i].second;
        } else {
            store.push_back(v[i]);
        }
    }

    vector<int> aux_base(n);
    for (int x : base) aux_base[x] = 1;
    vers[0] = build1(0, n-1, aux_base);
    // cerr << "done\n";
    for (int i = 1; i <= sz(ord); i++) {
        vers[i] = upd1(vers[i-1], 0, n-1, ord[i-1], 0);
    }
    // cerr << "done\n";
    for (int i = 0; i < n; i++) {
        sorted[i] = {a[i], i};
    }
    sort(sorted, sorted + n);
    vector<int> av(a, a + n);
    vers2[n] = build2(0, n-1, av);
    for (int i = n-1; i >= 0; i--) {
        vers2[i] = upd2(vers2[i+1], 0, n-1, sorted[i].second, sorted[i].first);
    }
}

int max_towers(int l, int r, int d) {
    if (r - l + 1 <= 2) return 1;
    // find the last thing < d
    int idx = lower_bound(store.begin(), store.end(), pair<int, int>{d, -1}) - store.begin() - 1;
    int gone = sz(base) - store[idx].second;

    D1 dd = qry1(vers[gone], 0, n-1, l, r);
    int ans = dd.sum;
    int first = dd.mn, last = dd.mx;

    if (ans == 0) {
        auto [mn_v, mn_idx] = qry_min(l, r);
        bool one = 0, two = 0;
        int idx1 = lower_bound(sorted, sorted + n, pair<int, int>{mn_v + d, -1}) - sorted;
        one = qry2(vers2[idx1], 0, n-1, l, mn_idx).right_big >= d;
        two = qry2(vers2[idx1], 0, n-1, mn_idx, r).left_big >= d;
        return int(one) + 1 + two;
    }

    bool one = 0, two = 0;
    int idx1 = lower_bound(sorted, sorted + n, pair<int, int>{a[first] + d, -1}) - sorted;
    int idx2 = lower_bound(sorted, sorted + n, pair<int, int>{a[last] + d, -1}) - sorted;
    one = qry2(vers2[idx1], 0, n-1, l, first).right_big >= d;
    two = qry2(vers2[idx2], 0, n-1, last, r).left_big >= d;

    /*
    bool one = 0, two = 0;
    for (int i = l; i < first; i++) {
        int x = qry_max(i, first);
        if (a[i] <= x - d && x - d >= a[first]) {
            one = 1;
            break;
        }
    }

    for (int i = last+1; i <= r; i++) {
        int x = qry_max(last, i);
        if (a[i] <= x - d && x - d >= a[last]) {
            two = 1;
            break;
        }
    }
    */

    ans += one;
    ans += two;

    return ans;
}

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