Submission #850942

#	Time	Username	Problem	Language	Result	Execution time	Memory
850942		olnyfcxwps	Radio Towers (IOI22_towers)	C++17	15 / 100	4073 ms	2552 KiB

towers

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Tower {
    int pos;
    int h;
}towers[100000];

int height[100000];
int tower_cnt;
bool ok;
bool picked[100000];
int k;

void special_case(){
    while (k < tower_cnt-1 and height[k] < height[k+1]){
        k += 1;
    }
    ok = true;
    for (int i = k;i < tower_cnt-1;i++){
        if (height[i] <= height[i+1]){
            ok = false;
        }
    }
}
void init(int N, vector<int> H) {
    tower_cnt = N;
    for (int i = 0; i < N; i++) {
        height[i] = H[i];
        towers[i].h = H[i];
        towers[i].pos = i;
    }
    special_case();
}

bool cmp(struct Tower t1, struct Tower t2) {
    return t1.h < t2.h;
}

int max_towers(int L, int R, int D) {
    if (ok){
        if ((L <= k and R <= k) or (L >= k and R >= k)){
            return 1;
        }
        else if (height[L] <= height[k]-D and height[R] <= height[k]-D){
            return 2;
        }else{
            return 1;
        }
    }else {
        int ans = 0;
        sort(towers, towers + tower_cnt, cmp);
        /*for (int i = 0; i < tower_cnt; i++) {
            cout << towers[i].pos << "\n";
        }*/
        for (int i = 0; i < tower_cnt; i++) {
            int pos = towers[i].pos;
            if (pos < L || pos > R) {
                continue;
            }
            int h = towers[i].h;
            bool valid = true;

            int max_left = h;
            for (int j = pos - 1; j >= L; j--) {
                if (picked[j]) {
                    if (max_left - D < height[j] || max_left - D < h) {
                        valid = false;
                        break;
                    }
                }
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }

            int max_right = h;
            for (int j = pos + 1; j <= R; j++) {
                if (picked[j]) {
                    if (max_right - D < height[j] || max_right - D < h) {
                        valid = false;
                        break;
                    }
                }
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }

            if (valid) {
                picked[pos] = true;
                // cout << pos << "\n";
                ans += 1;
            }
        }
        return ans;
    }
}

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