Submission #1078865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078865		mickey080929	Radio Towers (IOI22_towers)	C++17	23 / 100	4066 ms	2644 KiB

towers

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

using namespace std;

const int inf = 2e9 + 10;

int N;
vector<int> H;
vector<int> l, r;

void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    l.resize(N); r.resize(N);
    for (int i=0; i<N; i++) {
        l[i] = -1; r[i] = N;
        for (int j=i-1; j>=0; j--) {
            if (H[j] > H[i]) {
                l[i] = j;
                break;
            }
        }
        for (int j=i+1; j<N; j++) {
            if (H[j] > H[i]) {
                r[i] = j;
                break;
            }
        }
    }
}

int max_towers(int L, int R, int D) {
    int ans = 1;
    for (int i=L; i<=R; i++) {
        bool fl = false, fr = false;
        for (int j=max(L-1, l[i])+1; j<=i-1; j++) {
            if (H[j] <= H[i] - D) {
                fl = true;
                break;
            }
        }
        for (int j=i+1; j<=min(R+1, r[i])-1; j++) {
            if (H[j] <= H[i] - D) {
                fr = true;
                break;
            }
        }
        if (fl && fr) ans ++;
    }
    return ans;
}

• 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