Submission #1022903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022903		mansur	Radio Towers (IOI22_towers)	C++17	27 / 100	4017 ms	3712 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 = 2e5;

pii t[4 * 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;
}

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();
}


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 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;
    }
    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