Submission #1223035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223035		onbert	Radio Towers (IOI22_towers)	C++20	56 / 100	404 ms	39592 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, maxN = 4e5 + 5, INF = 1e15;
int n;
int a[maxn], sum[maxn];

pair<int,int> seg[maxN][2];
pair<int,int> def[2] = {{INF, INF}, {-INF, -INF}};
void build(int id, int l, int r, int j) {
    if (l == r) {
        seg[id][j] = {a[l], l};
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
    if (j == 0) seg[id][j] = min(seg[id*2][j], seg[id*2+1][j]);
    if (j == 1) seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
pair<int,int> qry(int id, int l, int r, int findl, int findr, int j) {
    if (findr < l || r < findl) return def[j];
    if (findl <= l && r <= findr) return seg[id][j];
    int mid = (l+r)/2;
    if (j == 0) return min(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
    else return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}

pair<int,int> mx(int l, int r) {
    return qry(1, 1, n, l, r, 1);
}
int mn(int l, int r) {
    return qry(1, 1, n, l, r, 0).first;
}

void init(int32_t N, std::vector<int32_t> H) {
    n = N;
    for (int i=0;i<n;i++) a[i+1] = H[i];
    sum[0] = 0;
    for (int i=1;i<=n;i++) sum[i] = (i > 1 && i < n && a[i] > a[i-1] && a[i] > a[i+1]) + sum[i-1];

    build(1, 1, n, 0);
    build(1, 1, n, 1);
}

int d;
vector<pair<int,int>> vec;

void solve(int l, int r) {
    if (l > r) return;
    auto [val, mid] = mx(l, r);
    solve(l, mid-1); solve(mid+1, r);
    // cout << l << " " << r << " " << lim << " " << lhs + rhs << " " << (int)(mn(l, r) <= lim) << endl;
    int lhs = mn(l, mid-1), rhs = mn(mid+1, r);
    if (lhs <= val - d && rhs <= val - d) {
        int L = l, R = mid-1;
        while (L < R) {
            int M = (L+R+1)/2;
            if (mn(M, mid-1) <= val - d) L = M;
            else R = M - 1;
        }
        int ll = L;
        L = mid+1, R = r;
        while (L < R) {
            int M = (L+R)/2;
            if (mn(mid+1, M) <= val - d) R = M;
            else L = M + 1;
        }
        int rr = R;
        vec.push_back({ll, rr});
    }
}

struct node {
    int val, lhs, rhs;
};
node seg2[8000005];
int cnt = 0;
void build2(int id, int l, int r) {
    seg2[id] = {(int)0, id*2, id*2+1};
    cnt = max(id, cnt);
    if (l == r) return;
    int mid = (l+r)/2;
    build2(id*2, l, mid); build2(id*2+1, mid+1, r);
}
int update2(int id, int l, int r, int target) {
    if (r < target || target < l) return id;
    cnt++;
    seg2[cnt] = seg2[id];
    id = cnt;
    seg2[id].val++;
    if (l == r) return id;
    int mid = (l+r)/2;
    seg2[id].lhs = update2(seg2[id].lhs, l, mid, target);
    seg2[id].rhs = update2(seg2[id].rhs, mid+1, r, target);
    return id;
}
int qry2(int id, int l, int r, int findl, int findr) {
    if (r < findl || findr < l) return 0;
    if (findl <= l && r <= findr) return seg2[id].val;
    int mid = (l+r)/2;
    return qry2(seg2[id].lhs, l, mid, findl, findr) + qry2(seg2[id].rhs, mid+1, r, findl, findr);
}

bool cmp(pair<int,int> x, pair<int,int> y) {
    return x.first > y.first;
}

bool inited = false;
int sz;
int t[maxn];
void init2() {
    inited = true;
    solve(1, n);
    sort(vec.begin(), vec.end(), cmp);
    sz = vec.size();
    build2(1, 1, n);
    for (int i=1;i<=n;i++) t[i] = 0;
    int last = 1;
    for (int i=0;i<sz;i++) {
        t[vec[i].first] = max(update2(last, 1, n, vec[i].second), t[vec[i].first]);
        last = t[vec[i].first];
        // cout << vec[i].first << " " << vec[i].second << endl;
    }
    for (int i=n-1;i>=1;i--) t[i] = max(t[i], t[i+1]);
    // for (int i=1;i<=n;i++) cout << t[i] << " "; cout << endl;
    // for (int i=1;i<=n;i++) cout << qry2(t[1], 1, n, i, i) << " "; cout << endl;
}

int32_t max_towers(int32_t L, int32_t R, int32_t D) {
    if (!inited) {d = D; init2();}
    L++, R++;
    return 1 + qry2(t[L], 1, n, 1, R);
}

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