Submission #1076757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076757		vjudge1	Radio Towers (IOI22_towers)	C++17	100 / 100	2526 ms	80976 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")


using namespace std;

using vi = vector<int>;
const int INF = 1e9;

int n;
vi H;

vi St, Dr;
vi DeltaSt, DeltaDr;

struct RMQ {
    int n;
    vector<vi> A;
    RMQ(vi V0) : n((int)V0.size()) {
        A.push_back(V0);
        for(int k = 1; (1 << k) <= n; ++k) {
            A.push_back(A.back());
            for(int i = 0; i < n; ++i) {
                if(i + (1 << (k - 1)) < n)
                    A[k][i] = max(A[k][i], A[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    int query(int l, int r) {
        int d = 31 - __builtin_clz(r - l + 1);
        return max(A[d][l], A[d][r - (1 << d) + 1]);
    }
};

pair<vi, vi> descomp(vi A) {
    RMQ R(A);
    vi Ant(n, -1);
    vi Delta(n, INF); /// cel mai mare delta posibil
    stack<int> S;
    for(int i = 0; i < n; ++i) {
        while(!S.empty() && A[S.top()] > A[i]) {
            S.pop();
        }
        if(!S.empty()) {
            Ant[i] = S.top();
            Delta[i] = R.query(S.top(), i) - A[i];
        }
        S.push(i);
    }
    return make_pair(Ant, Delta);
}

vi S;

const int MN = 100000;

struct AIB2D {
    int n;
    vi V[4 * MN];
    AIB2D() {}
    AIB2D(const vi &V0) : n((int)V0.size()) {
        build(V0, 1, 0, n - 1);
    }

    void build(const vi &V0, int u, int s, int d) {
        for(int i = s; i <= d; ++i)
            V[u].push_back(V0[i]);
        sort(V[u].begin(), V[u].end());
        if(s != d) {
            build(V0, u << 1, s, (s + d) >> 1);
            build(V0, u << 1 | 1, ((s + d) >> 1) + 1, d);
        }
    }
    int query(int l, int r, int D, int u, int s, int d) {
        if(d < l || r < s) return 0;
        if(l <= s && d <= r) {
            int v = lower_bound(V[u].begin(), V[u].end(), D) - V[u].begin();
            return int(V[u].size()) - v;
        }
        return query(l, r, D, u << 1, s, (s + d) >> 1)
            + query(l, r, D, u << 1 | 1, ((s + d) >> 1) + 1, d);
    }
    int query(int l, int r, int D) {
        return query(l, r, D, 1, 0, n - 1);
    }
};

AIB2D ASt, ADr;
AIB2D ATot;


void init(int N0, vi H0) {
    n = N0;
    H = H0;

    tie(St, DeltaSt) = descomp(H);
    reverse(H.begin(), H.end());
    tie(Dr, DeltaDr) = descomp(H);
    reverse(H.begin(), H.end());
    reverse(Dr.begin(), Dr.end());
    reverse(DeltaDr.begin(), DeltaDr.end());
    for(auto &it : Dr) 
        it = n - it - 1;
    S.resize(n);
    for(int i = 0; i < n; ++i)
        S[i] = min(DeltaSt[i], DeltaDr[i]);
    ASt = AIB2D(DeltaSt);
    ADr = AIB2D(DeltaDr);
    ATot = AIB2D(S);
}


int max_towers(int l, int r, int D) {
    int v = ATot.query(l, r, D);
    if(v == 0) {
        ///poate gasim un SolDr >= D si dupa un SolSt >= D
        int st = l, dr = r, mij;
        if(ADr.query(l, r, D) == 0) return 1;
        while(st < dr) {
            mij = (st + dr) / 2;
            if(ADr.query(l, r, D)) dr = mij;
            else st = mij + 1;
        }
        if(ASt.query(st + 1, r, D)) return 2;
        return 1;
    }
    int st, dr, mij;

    int p1;
    st = l, dr = r;
    while(st < dr) {
        mij = (st + dr) / 2;
        if(ATot.query(l, mij, D)) dr = mij;
        else st = mij + 1;
    }
    p1 = st;

    int p2;
    st = l; dr = r;
    while(st < dr) {
        mij = (st + dr + 1) / 2;
        if(ATot.query(mij, r, D)) st = mij;
        else dr = mij - 1;
    }
    p2 = st;

    int found_st = 0, found_dr = 0;
    found_st = !!ADr.query(l, p1 - 1, D);
    found_dr = !!ASt.query(p2 + 1, r, D);
    return v + found_st + found_dr;
}

• 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