Submission #748797

#	Time	Username	Problem	Language	Result	Execution time	Memory
748797		QwertyPi	Radio Towers (IOI22_towers)	C++17	17 / 100	1209 ms	13820 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

namespace solve{
	int N; vector<int> H;
	map<int, int> ans; 
	void init(){
		set<pair<int, int>> T;
		set<pair<int, pair<int, int>>> S;
		vector<bool> active(N, true);
		for(int i = 0; i < N; i++){
			if(i > 0 && i < N - 1 && ((H[i - 1] <= H[i] && H[i] <= H[i + 1]) || (H[i - 1] >= H[i] && H[i] >= H[i + 1]))) {
				active[i] = false;
				continue;
			}
			T.insert({i, H[i]});
		}
		
		if (T.size() >= 2 && (T.begin())->se > next(T.begin())->se) {
			active[T.begin()->fi] = false;
			T.erase(T.begin());
		}
		
		if (T.size() >= 2 && prev(T.end())->se > prev(prev(T.end()))->se) {
			active[prev(T.end())->fi] = false;
			T.erase(prev(T.end()));
		}
		/*
		cout << "D = 0" << endl;
		for(auto t : T){
			cout << "[" << t.fi << "] => " << t.se << endl;
		}
		*/
		ans[0] = (T.size() + 1) / 2;
		for(auto t = T.begin(); t != T.end(); t++){
			if(t != T.begin()) {
				S.insert({abs(t->se - prev(t)->se), {t->fi, prev(t)->fi}});
			}
		}
		vector<int> Ir;
		while(S.size()){
			auto [d, p] = *S.begin(); S.erase(S.begin());
			Ir.push_back(d);
			
			int x = p.fi, y = p.se;
			if(!active[x] || !active[y])
				continue;
			
			active[x] = active[y] = false;

			auto ptr = T.lower_bound({x, -1});
			if(ptr != T.end() && ptr->fi == x)
				T.erase(ptr);
			
			ptr = T.lower_bound({y, -1});
			if(ptr != T.end() && ptr->fi == y)
				T.erase(ptr); 
			
			ptr = T.lower_bound({y, -1});
			if (ptr != T.begin() && ptr != T.end()) {
				S.insert({abs(ptr->se - prev(ptr)->se), {ptr->fi, prev(ptr)->fi}});
			}
			/*
			cout << "D = " << d << endl;
			for(auto t : T){
				cout << "[" << t.fi << "] => " << t.se << endl;
			}
			*/
			assert(T.size() % 2 == 1);
			ans[d + 1] = (T.size() + 1) / 2;
		}
	}
	
	int query(int L, int R, int D) {
		return (--ans.upper_bound(D))->se;
	}
};

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

int max_towers(int L, int R, int D) {
	return solve::query(L, R, D);
}

• 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