Submission #1179550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179550		gyg	Radio Towers (IOI22_towers)	C++20	0 / 100	319 ms	6316 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5, INF = 2e9;

int n;
arr<int, N> h;

struct Sgt {
    arr<int, 4 * N> tr;
    void bld(int u = 1, int lw = 1, int hg = n) {
        if (lw == hg) { tr[u] = h[lw]; return; }
        int md = (lw + hg) / 2;
        bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
        tr[u] = max(tr[2 * u], tr[2 * u + 1]);
    }
    void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
        if (lw == hg) { tr[u] += x; return; }
        int md = (lw + hg) / 2;
        if (i <= md) upd(i, x, 2 * u, lw, md);
        else upd(i, x, 2 * u + 1, md + 1, hg);
        tr[u] = max(tr[2 * u], tr[2 * u + 1]);
    }
    int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
        if (l > r) return 0;
        if (l <= lw && hg <= r) return tr[u];
        int md = (lw + hg) / 2, ans = 0;
        if (l <= md) ans = max(ans, qry(l, r, 2 * u, lw, md));
        if (r > md) ans = max(ans, qry(l, r, 2 * u + 1, md + 1, hg));
        return ans;
    }
} sgt;


map<int, int> bfr;
set<int> mns;
set<pii> gps;
int dff(int l, int r) {
    return sgt.qry(l, r) - max(h[l], h[r]);
}
vec<pii> src;

void init(int _n, vec<int> _h) {
    n = _n;
    for (int i = 1; i <= n; i++) h[i] = _h[i - 1];

    sgt.bld();
    for (int i = 1; i <= n; i++)
        if ((i == 1 || h[i] < h[i - 1]) && (i == n || h[i] < h[i + 1]))
            mns.insert(i);
    for (auto it = mns.begin(); it != mns.end(); it++) {
        if (next(it, 1) == mns.end()) continue;
        gps.insert({dff(*it, *next(it, 1)), *it});
    }

    int tmr = 0;
    while (gps.size()) {
        pii x = *gps.begin(); gps.erase(gps.begin());
        int i = x.sec;
        // cout << x.fir << ": " << mns.size() << '\n';
        if (x.fir >= tmr) {
            tmr = x.fir;
            bfr[x.fir] = mns.size();
        }
        int j = *(++mns.find(i));

        if (h[i] < h[j]) {
            if (++mns.find(j) == mns.end()) { mns.erase(j); continue;}
            int k = *(++mns.find(j));
            mns.erase(j), gps.erase({dff(j, k), j});
            gps.insert({dff(i, k), i});
        } else {
            if (mns.find(i) == mns.begin()) { mns.erase(i); continue; }
            int k = *(--mns.find(i));
            mns.erase(i), gps.erase({dff(k, i), k});
            gps.insert({dff(k, j), k});
        }
    }
    bfr[INF] = 1;

    for (pii x : bfr) src.push_back(x);

    // for (int i : mns) cout << i << '\n';
    // for (pii x : gps) cout << x.fir << " " << x.sec << '\n';
    // for (pii x : bfr) cout << x.fir << " " << x.sec << '\n';
}

int max_towers(int l, int r, int d) {
    l++, r++; 

    int lw = 0, hg = src.size() - 1;
    while (lw < hg) {
        int md = (lw + hg) / 2;
        if (src[md].fir >= d) hg = md;
        else lw = md + 1;
    }
    return src[lw].sec;
}

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