Submission #1022996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022996		mansur	Radio Towers (IOI22_towers)	C++17	27 / 100	4089 ms	32460 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first 

using ll = long long;
using pii = pair<int, int>; 
using pll = pair<ll, ll>;

vector<int> h;
int n, k, ok = 1;
const int inf = 1e9, N1 = 3e7;

pii t[N1];

void bld(int u = 1, int tl = 0, int tr = n - 1) {
    if (tl == tr) {
        t[u] = {tl, tl};
        return;
    }
    int m = (tl + tr) / 2;
    bld(u * 2, tl, m);
    bld(u * 2 + 1, m + 1, tr);
    t[u] = t[u * 2 + 1];
    if (h[t[u * 2].f] > h[t[u].f]) t[u].f = t[u * 2].f;
    if (h[t[u * 2].s] < h[t[u].s]) t[u].s = t[u * 2].s;
}

pii get(int l, int r, int u = 1, int tl = 0, int tr = n - 1) {
    if (tl > r || tr < l) return {-1, -1};
    if (tl >= l && tr <= r) return t[u];
    int m = (tl + tr) / 2;
    auto [x1, x2] = get(l, r, u * 2, tl, m);
    auto [y1, y2] = get(l, r, u * 2 + 1, m + 1, tr);
    if (x1 == -1) return {y1, y2};
    if (y1 == -1) return {x1, x2};
    if (h[y1] > h[x1]) x1 = y1;
    if (h[y2] < h[x2]) x2 = y2;
    return {x1, x2};
}

int t2[N1], vl[N1], vr[N1], cur = 1;

void upd(int l, int r, int u = 1, int tl = 1, int tr = inf) {
    if (tl > r || tr < l || r < l) return;
    if (tl >= l && tr <= r) {
        t2[u]++;
        return;
    }
    int m = (tl + tr) / 2;
    if (!vl[u]) vl[u] = ++cur;
    if (!vr[u]) vr[u] = ++cur;
    upd(l, r, vl[u], tl, m);
    upd(l, r, vr[u], m + 1, tr);
}

int gt(int p, int u = 1, int tl = 1, int tr = inf) {
    if (tl == tr) return t2[u];
    int m = (tl + tr) / 2;
    if (p <= m) {
        if (vl[u]) return gt(p, vl[u], tl, m) + t2[u];
        return t2[u];
    }
    if (vr[u]) return gt(p, vr[u], m + 1, tr) + t2[u];
    return t2[u];
}

void calc(int l, int r, int mx) {
    if (r < l) return;
    if (l == r) {
        upd(1, mx - h[l]);
        return; 
    }
    auto [pos, ps] = get(l, r);
    if (pos == l) calc(l + 1, r, mx);
    else if (pos == r) calc(l, r - 1, mx);
    else {
        upd(h[pos] - h[ps] + 1, mx - h[ps]);
        calc(l, pos - 1, h[pos]);
        calc(pos + 1, r, h[pos]);
    }
}

void init(int N, vector<int> H) {
    n = N, h = H;
    k = n - 1;
    for (int i = 1; i < n; i++) {
        if (h[i] < h[i - 1]) {
            k = i - 1;
            break;
        }
    }
    for (int i = 1; i < k; i++) {
        if (h[i - 1] > h[i]) ok = 0;
    }
    for (int i = k + 1; i < n; i++) {
        if (h[i - 1] < h[i]) ok = 0;
    }
    bld();
    calc(0, n - 1, inf);
}

int f(int l, int r, int d, int mx) {
    if (r < l) return 0;
    if (l == r) return (h[l] <= mx);
    auto [pos, ps] = get(l, r);
    if (h[ps] > mx) return 0;
    if (pos == l) return f(l + 1, r, d, mx);
    if (pos == r) return f(l, r - 1, d, mx);
    return max(1, f(l, pos - 1, d, min(mx, h[pos] - d)) + f(pos + 1, r, d, min(mx, h[pos] - d)));
}

int max_towers(int l, int r, int d) {
    if (ok) {
        if (k == -1) return 1;
        if (k <= l || r <= k) return 1;
        if (h[l] > h[k] - d || h[r] > h[k] - d) return 1;
        return 2;
    }
    if (l == 0 && r == n - 1) {
        return gt(d);
    }
    return f(l, r, d, inf);
}

• Subtask 1: 4 / 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