Submission #1076638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076638		vjudge1	Radio Towers (IOI22_towers)	C++17	23 / 100	4091 ms	11344 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;
    S.resize(n);
    for(int i = 0; i < n; ++i) {
        S[i] = min(DeltaSt[i], DeltaDr[i]);
    }
 //   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) {
    vi Sol;
    for(int i = l; i <= r; ++i) {
        if(S[i] >= D) {
            Sol.push_back(i);
        }
    }
    if(Sol.empty()) {
        ///poate gasim un SolDr >= D si dupa un SolSt >= D
        int tip = 0;
        for(int i = l; i <= r; ++i) {
            if(DeltaDr[i] >= D) {
                if(tip == 0) {
                    tip = 1;
                    continue;
                }
            }
            if(DeltaSt[i] >= D && tip == 1) {
                tip = 2;
                continue;
            }
        }
        if(tip == 2) return 2;
        return 1;
    }
    int found_st = 0, found_dr = 0;
    for(int i = l; i < Sol[0]; ++i)
        if(DeltaDr[i] >= D) found_st = 1;
    for(int i = Sol.back() + 1; i <= r; ++i)
        if(DeltaSt[i] >= D) found_dr = 1;
    return int(Sol.size()) + found_st + found_dr;
}

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