Submission #639766

#	Time	Username	Problem	Language	Result	Execution time	Memory
639766		study	Radio Towers (IOI22_towers)	C++17	54 / 100	4078 ms	9416 KiB

towers

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

const int MAXN = 1e5, half = 1e5+1;
int n, a[MAXN],segt[200003],psum[MAXN+1];
vector<pair<int,int>> answers;

int query(int l, int r){
	l += half;
	r += half;
	int ans = 0;
	while (l <= r){
		if (l&1){
			ans = max(ans,segt[l]);
			l++;
		}
		if (r%2 == 0){
			ans = max(ans,segt[r]);
			r--;
		}
		l >>= 1;
		r >>= 1;
	}
	return ans;
}

void modify(int node, int val){
	node += half;
	segt[node] = val;
	node >>= 1;
	while (node){
		segt[node] = max(segt[2*node],segt[2*node+1]);
		node >>= 1;
	}
}

void init(int N, vector<int> H){
	n = N;
	for (int i=0; i<n; ++i){
		a[i] = H[i];
		modify(i,a[i]);
	}
	for (int i=0; i<n; ++i){
		if ((i == 0 or a[i] < a[i-1]) and (i == n-1 or a[i] < a[i+1])){
			psum[i+1]++;
		}
		psum[i+1] += psum[i];
	}
	vector<pair<int,int>> v,deltas;
	for (int i=0; i<n; ++i){
		v.emplace_back(a[i],i);
	}
	sort(v.begin(),v.end());
	set<int> pos = {INT_MIN,INT_MAX};
	for (auto i:v){
		auto it = pos.upper_bound(i.second);
		int A = *it,maxi=INT_MAX;
		it--;
		int B = *it;
		bool ok = false;
		if (A != INT_MAX){
			if (i.second == A-1) ok = true;
			maxi = min(maxi,query(i.second,A));
		}
		if (B != INT_MIN){
			if (B == i.second-1) ok = true;
			maxi = min(maxi,query(B,i.second));
		}
//		cout << maxi << ' ' << i.first << endl;
		if (maxi != i.first and !ok){
			if (maxi == INT_MAX) deltas.emplace_back(maxi,i.second);
			else deltas.emplace_back(max(1,maxi-i.first),i.second);
		}
		pos.emplace(i.second);
	}
	sort(deltas.rbegin(),deltas.rend());
//	for (auto i:deltas) cout << i.first << ' ' << i.second << endl;
	int val = INT_MAX, occ = 0;
	for (auto i:deltas){
		if (val == i.first){
			++occ;
		}
		else{
			answers.emplace_back(val,occ);
			val = i.first;
			occ++;
		}
	}
	answers.emplace_back(val,occ);
	reverse(answers.begin(),answers.end());
//	for (auto i:answers) cout << i.first << ' ' << i.second << endl;
}
int max_towers(int L, int R, int D){
	if (L == 0 and R == n-1){
//		for (auto i:answers) cout << i.first << ' ' << i.second << '\n';
		int idx = lower_bound(answers.begin(),answers.end(),make_pair(D,0))-answers.begin();
		return answers[idx].second;
	}
	if (D == 1){
		int ans = 0;
		if (L < R and a[L] < a[L+1]) ++ans;
		if (L < R and a[R] < a[R-1]) ++ans;
		L++; R++;
		if (L == R) return 1;
		return psum[R-1]-psum[L]+ans;
	}
	set<int> st;
	vector<pair<int,int>> v;
	for (int i=L; i<=R; ++i){
		v.emplace_back(a[i],i);
	}
	sort(v.begin(),v.end());
	int ans = 0;
	for (auto k:v){
		int i = k.second;
		if (st.empty()){
			st.emplace(i);
			++ans;
			continue;
		}
		auto it = st.upper_bound(i);
		int A = *it;
		--it;
		int B = *it;
		if ((*st.rbegin() < i or query(i,A)-D >= max(a[A],a[i])) and (*st.begin() > i or query(B,i)-D >= max(a[B],a[i]))){
			st.emplace(i);
			++ans;
		}
	}
	return ans;
}

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