Submission #626285

#	Time	Username	Problem	Language	Result	Execution time	Memory
626285		kevinxiehk	Radio Towers (IOI22_towers)	C++17	4 / 100	4098 ms	9508 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define int long long
using namespace std;

int n;
vector<int> h;
int pv[100005]; // 0: peak, 1: valley, 2: upslope, 3: downslope
int ps[100005];
int mx = 0;
int q = 0;
pair<int, int> seg[400005];
vector<pair<int, int>> ee;
int nn;

void build(int l, int r, int id) {
    if(l == r) seg[id] = mp(h[ee[l].fi], l);
    else {
        int m = (l + r) / 2;
        build(l, m, id * 2);
        build(m + 1, r, id * 2 + 1);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    return;
}
void upd(int l, int r, int id, int k, int val) {
    if(l == r) seg[id] = mp(val, l);
    else {
        int m = (l + r) / 2;
        if(k <= m) upd(l, m, id * 2, k, val);
        else upd(m + 1, r, id * 2 + 1, k, val);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    return;
}
pair<int, int> rmq (int l, int r, int id, int ql, int qr) {
    // cerr << l << ' ' << r << ' ' << id << ' ' << ql << ' ' << qr << '\n';
    if(ql > r || qr < l) return mp(-1, -1);
    if(ql <= l && qr >= r) return seg[id];
    int m = (l + r) / 2;
    return max(rmq(l, m, id * 2, ql, qr), rmq(m + 1, r, id * 2 + 1, ql, qr));
}
int lp[200005];

void init(signed N, vector<signed> H) {
    n = N;
    h.pb(2000000000);
    for(auto x: H) h.pb(x);
    h.pb(2000000000);
    ee.pb(mp(0, 0));
    for(int i = 1; i <= n; i++) {
        mx = max(mx, h[i]);
        if(h[i] < h[i - 1] && h[i] < h[i + 1]) pv[i] = 1;
        else if(h[i] > h[i - 1] && h[i] < h[i + 1]) pv[i] = 2;
        else if(h[i] < h[i - 1] && h[i] > h[i + 1]) pv[i] = 3;
        ps[i] = ps[i - 1];
        if(pv[i] == 1) ps[i]++;
        if(pv[i] <= 1) {
            ee.pb(mp(i, pv[i]));
        }
    }
    nn = ee.size() - 1;
    for(int i = 1; i <= 100000; i *= 2) {
        for(int j = i; j < i * 2; j++) lp[j] = i;
    }
    build(1, nn, 1);
    for(int i = 2; i <= nn; i++) {
        assert((pv[ee[i].fi] ^ pv[ee[i - 1].fi]) == 1);
    }
    // for(int i = 1; i <= n; i++) cerr << pv[i] << ' '; cerr << '\n';
    // cerr << nn << '\n';
    return;
}
int solve(int l, int r, int mx, int d) {
    assert(pv[ee[l].fi] == pv[ee[r].fi] && pv[ee[r].fi] == 1);
    // cerr << l << ' ' << r << ' ' << mx << ' ' << d  << '\n';
    if(mx <= 0) return 0;
    if(l > r) return 0;
    // if(l == r && pv[ee[l].se] == 1) return (h[ee[l].se] <= mx);
    assert(l >= 1 && r <= nn);
    auto aa = rmq(1, nn, 1, l, r);
    
    if(pv[ee[aa.se].fi] == 1) {
        assert(l == r);
        // cerr << l << ' ' << r << ' ' << mx << ' ' << d << ' ' << aa.fi << ' ' << aa.se << ' ' << (h[ee[l].fi] <= mx) << '\n';
        return (aa.fi <= mx);
    }
    int a = solve(l, aa.se - 1, min(mx, aa.fi - d), d) + solve(aa.se + 1, r, min(mx, aa.fi - d), d);
    int b = max(solve(l, aa.se - 1, mx, d), solve(aa.se + 1, r, mx, d));
    // cerr << l << ' ' << r << ' ' << mx << ' ' << d << ' ' << aa.fi << ' ' << aa.se << ' ' << max(a, b) << '\n';
    return max(a, b);
}

signed max_towers(signed l, signed r, signed d) {
    l++; r++; q++;
    if(r - l < 2) return 1;
    int el = 0;
    int er = 0;
    for(int i = lp[nn]; i > 0; i /= 2) {
        if(el + i <= nn && ee[el + i].fi < l) el += i;
        if(er + i <= nn && ee[er + i].fi <= r) er += i;
        // cerr << i << ' ' << nn << ' ' << el << ' ' << er << ' ' << ee[el].fi << ' ' << ee[er].fi << ' ' << l << ' ' << r << '\n';
    }
    el++;
    if(el > er) return 1;
    bool lc = false;
    bool rc = false;
    if(pv[l] == 2) {
        lc = true;
        el--;
        pv[l] = 1;
        upd(1, nn, 1, el, h[l]);
    }
    if(pv[r] == 3) {
        rc = true;
        er++;
        pv[r] = 1;
        upd(1, nn, 1, er, h[r]);
    }
    // cerr << el << ' ' << er << '\n';
    if(pv[ee[el].fi] == 0) el++;
    if(pv[ee[er].fi] == 0) er--;
    // cerr << el << ' ' << er << '\n';
    int kk;
    if(el >= er) kk = 1;
    else kk = solve(el, er, 1000000001, d);

    if(lc) {
        pv[l] = 2;
        upd(1, nn, 1, el, h[ee[el].fi]);
    }
    if(rc) {
        pv[r] = 3;
        upd(1, nn, 1, er, h[ee[er].fi]);
    }
    return max(1LL, kk);
}

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