Submission #639768

#	Time	Username	Problem	Language	Result	Execution time	Memory
639768		study	Radio Towers (IOI22_towers)	C++17	4 / 100	839 ms	1468 KiB

towers

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

const int MAXN = 1e5;
int n, a[MAXN],l[MAXN];
bool ok = true;
int maxi = 0,idx=0;

void init(int N, vector<int> H){
	n = N;
	ok = false;
	maxi = 0;
	for (int i=0; i<n; ++i){
		a[i] = H[i];
		maxi = max(maxi,a[i]);
		if (a[i] == maxi) idx = i;
	}
}
int max_towers(int L, int R, int D){
	if (R < idx or L > idx) return 1;
	if (max(a[L],a[R]) <= maxi-D) return 2;
	return 1;
	int ans = 0;
	if (!ok){
		fill_n(&l[0],MAXN,0);
		ok = true;
		set<int> st;
		st.emplace(INT_MAX);
		st.emplace(INT_MIN);
		vector<pair<int,int>> v;
		for (int i=0; i<n; ++i){
			v.emplace_back(a[i],i);
		}
		sort(v.begin(),v.end());
		int idx = 0;
		for (auto i:v){
			while (idx < n and v[idx].first <= i.first-D){
				st.emplace(v[idx].second);
				idx++;
			}
			auto a = st.upper_bound(i.second), b = a;
			--a;
			if ((*b) != INT_MAX){
				l[*b] = *a;
			}
		}
	}
	vector<int> dp(R+1,1);
	for (int i=L; i<=R; ++i){
		int prev = l[i];
		if (prev >= L){
			dp[i] = dp[prev]+1;
		}
		if (i) dp[i] = max(dp[i],dp[i-1]);
	}
	return dp[R];
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:23:6: warning: unused variable 'ans' [-Wunused-variable]
   23 |  int ans = 0;
      |      ^~~

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