Submission #1015628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015628		inesfi	Radio Towers (IOI22_towers)	C++17	23 / 100	4078 ms	19976 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;

const int DECALAGE=(1<<17);
int pb,avant,apres,rep;
vector<int> h;
vector<pair<int,int>> altitudes;
int arbremax[DECALAGE*2];
set<int> pris;
set<int>::iterator it;

int maxi(int deb,int fin){
    if (deb==fin){
        return arbremax[deb];
    }
    if (deb%2==1){
        return max(arbremax[deb],maxi(deb+1,fin));
    }
    if (fin%2==0){
        return max(arbremax[fin],maxi(deb,fin-1));
    }
    return maxi(deb/2,fin/2);
}

void init(int N,vector<int> H) {
    h=H;
}

int max_towers(int L, int R, int D) {
    for (int i=L;i<=R;i++){
        altitudes.push_back(make_pair(h[i],i));
        arbremax[i+DECALAGE]=h[i];
    }
    for (int i=DECALAGE-1;i>=0;i--){
        arbremax[i]=max(arbremax[i*2],arbremax[i*2+1]);
    }
    sort(altitudes.begin(),altitudes.end());
    for (int i=0;i<(int)altitudes.size();i++){
        it=pris.lower_bound(altitudes[i].second);
        pb=0;
        if (it!=pris.end()){
            apres=*(it);
            if (maxi(altitudes[i].second+DECALAGE,apres+DECALAGE)-altitudes[i].first<D){
                pb=1;
            }
        }
        if (it!=pris.begin()){
            it--;
            avant=*(it);
            if (maxi(avant+DECALAGE,altitudes[i].second+DECALAGE)-altitudes[i].first<D){
                pb=1;
            }
        }
        if (pb==0){
            pris.insert(altitudes[i].second);
            rep++;
        }
    }
    return rep;
}

• 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