Submission #659083

#	Time	Username	Problem	Language	Result	Execution time	Memory
659083		keta_tsimakuridze	Radio Towers (IOI22_towers)	C++17	100 / 100	2100 ms	159456 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 5, inf = 1e9;
int T[20 * N][3], lc[20 * N][3], rc[20 * N][3];
int c[3], r[N][3], n,  A[N], tree[4 * N][2];
vector<int> x, a, ll, rr;
vector<pair<int,int>>add[N][3];
void build(int u, int l, int r) {
    if(l == r) {
        tree[u][0] = l;
        tree[u][1] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    tree[u][0] = (a[tree[2 * u][0]] < a[tree[2 * u + 1][0]] ? tree[2 * u][0] : tree[2 * u + 1][0]);
    tree[u][1] = max(tree[2 * u][1], tree[2 * u + 1][1]);
}
int MX(int u, int st, int en,int l,int r,int t) {
    if(l > en || r < st) return (t == 0 ? n : 0);
    if(st <= l && r <= en) return tree[u][t];
    int mid = (l + r) / 2;
    int x = MX(2 * u, st, en, l, mid, t), y =  MX(2 * u + 1, st, en, mid + 1, r, t);
    if(t == 0) return (a[x] < a[y] ? x : y);
    return max(x, y);
}
void build(int u, int l, int r, int t) {
    T[u][t] = (t == 1 ? n : 0);
    if(l == r) return;
    lc[u][t] = ++c[t]; rc[u][t] = ++c[t];
    build(lc[u][t], l, (l + r) / 2, t); build(rc[u][t], (l + r) / 2 + 1, r, t);
}
int merge(int a, int b, int t) {
    return (t == 0 ? max(a, b) : t == 1 ? min(a, b) : a + b);
}
void upd(int u, int id, int l, int r, int t, int v) {
    if(l == r) {
        T[c[t]][t] = v;
        return;
    }
    int mid = (l + r) / 2, x = c[t];
    lc[x][t] = lc[u][t], rc[x][t] = rc[u][t];
    if(id <= mid) lc[x][t] = ++c[t], upd(lc[u][t], id, l, mid, t, v);
    else rc[x][t] = ++c[t], upd(rc[u][t], id, mid + 1, r, t, v);
    T[x][t] = merge(T[lc[x][t]][t], T[rc[x][t]][t], t);
}
int get(int u, int st, int en, int l, int r, int t) {
    if(l > en || r < st || l > r) return (t == 1 ? n : 0);
    if(st <= l && r <= en) return T[u][t];
    int mid = (l + r) / 2;
    return merge(get(lc[u][t], st, en, l, mid, t), get(rc[u][t], st, en, mid + 1, r, t), t);
}
void init(int nn, std::vector<int> A) {
    n = nn;
    vector<int> L(n), R(n), f(n);
    stack<int> st;
    a = A; a.push_back(inf);
    for(int i = 0; i < n; i++) {
        while(st.size() && a[st.top()] > a[i]) st.pop();
        L[i] = (st.size() ? st.top() : -1);
        st.push(i);
    }
    build(1, 0, n - 1);
    while(st.size()) st.pop();

    for(int i = n - 1; i >= 0; i--) {
        while(st.size() && a[st.top()] > a[i]) st.pop();
        R[i] = (st.size() ? st.top(): n );
        st.push(i);

        int dl = (L[i] != -1 ? MX(1, L[i], i - 1, 0, n - 1, 1) - a[i] : inf),
            dr = (R[i] != n ? MX(1, i + 1, R[i], 0, n - 1, 1) - a[i] : inf);
        x.push_back(dl);
        x.push_back(dr);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for(int i = 0; i < n; i++) {

        int dl = (L[i] != -1 ? MX(1, L[i], i - 1, 0, n - 1, 1) - a[i] : inf),
            dr = (R[i] != n ? MX(1, i + 1, R[i], 0, n - 1, 1) - a[i] : inf);

        dl = lower_bound(x.begin(), x.end(), dl) - x.begin();
        dr = lower_bound(x.begin(), x.end(), dr) - x.begin();
        // x <= min(dl, dr)

        add[min(dl, dr)][2].push_back({i,  1});
        if(dl == dr) continue;
        if(dl < dr) {
            // x <= dr
            add[dr][1].push_back({i, L[i]});
            add[dl][1].push_back({i, n});
            continue;
        }
        add[dl][0].push_back({i, R[i]});
        add[dr][0].push_back({i, 0});
    }
    // <=
    ll = L; rr = R;
    for(int t = 0; t <= 2; t++) r[x.size()][t] = ++c[t], build(c[t], 0, n - 1, t);
    for(int i = (int)x.size() - 1; i >= 0; i--) {
        for(int t = 0; t <= 2; t++) {
            r[i][t] = r[i + 1][t];
            for(int j = 0; j < add[i][t].size(); j++) {
                int x = ++c[t];

                upd(r[i][t], add[i][t][j].f, 0, n - 1, t, add[i][t][j].s);
                r[i][t] = x;
            }
        }
    }

}

int max_towers(int L, int R, int D) {
    int Dd = D;
    D = lower_bound(x.begin(), x.end(), D) - x.begin();
    assert(r[D][1]);
    int ans = get(r[D][2], L, R, 0, n - 1, 2);
    int id = MX(1, L, R, 0, n - 1, 0);
    ans += (!get(r[D][2], id, id, 0, n - 1, 2));
    /*
    int cl = 0, cr = 0;
    for(int i = id - 1; i >= L; i--) {
       if(get(r[D][2], i, i, 0, n - 1, 2)) continue;
       int dl = (ll[i] >= L ? MX(1, ll[i], i - 1, 0, n - 1, 1) - a[i] : inf), dr = (rr[i] != n ? MX(1, i + 1, rr[i], 0, n - 1, 1) - a[i] : inf);
        if(ll[i] < L && dr >= Dd) ++cl;
    }
    for(int i = id + 1; i <= R; i++) {
        if(get(r[D][2], i, i, 0, n - 1, 2)) continue;
        int dl = (ll[i] != -1 ? MX(1, ll[i], i - 1, 0, n - 1, 1) - a[i] : inf), dr = (rr[i] <= R ? MX(1, i + 1, rr[i], 0, n - 1, 1) - a[i] : inf);
        if(min(dl, dr) >= Dd) ++cr;
    } */
    ans += (get(r[D][1], L, id - 1, 0, n - 1, 1) < L)  + (get(r[D][0], id + 1, R, 0, n - 1, 0) > R);
    return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:107:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for(int j = 0; j < add[i][t].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:119:9: warning: unused variable 'Dd' [-Wunused-variable]
  119 |     int Dd = D;
      |         ^~

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