Submission #1076457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076457		vjudge1	Radio Towers (IOI22_towers)	C++17	17 / 100	710 ms	11328 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>


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;


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;
    for(int i = 0; i < n; ++i) {
        S.push_back(min(DeltaSt[i], DeltaDr[i]));
    }
    sort(S.begin(), S.end());
 //   cout << "St: ";
 //   for(auto it : St) cout << it << " ";
 //   cout << "\n";
 //   cout << "DeltaSt: ";
 //   for(auto it : DeltaSt) cout << it << " ";
 //   cout << "\n";
 //   cout << "Dr: ";
 //   for(auto it : Dr) cout << it << " ";
 //   cout << "\n";
 //   cout << "DeltaDr: ";
 //   for(auto it : DeltaDr) cout << it << " ";
 //   cout << "\n";
}

int max_towers(int L, int R, int D) {
    int v = lower_bound(S.begin(), S.end(), D) - S.begin();
    return n - v;
}

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