Submission #1082244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082244		s_tree	Radio Towers (IOI22_towers)	C++17	0 / 100	4080 ms	6980 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int root = 0;
int par[N];
int L[N], R[N], mn[N];

struct ST {
	vector<pair<int,int>> t;
	int n;
	ST(){}
	ST(vector<int>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++)t[i+n] = {h[i], i};
		for(int i = n-1;i>0;i--)t[i] = max(t[2*i], t[2*i+1]);
	}
	int query(int l, int r) {
		l+=n,r+=n+1;
		pair<int,int> ans = {-1, -1};	
		for(;l<r;l>>=1,r>>=1) {
			if(l&1)ans = max(ans, t[l++]);
			if(r&1)ans = max(ans, t[--r]);
		}
		return ans.second;
	}
};
struct ST2 {
	vector<int> t;
	int n;
	ST2(){}
	ST2(vector<int>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++)t[i+n] = h[i];
		for(int i = n-1;i>0;i--)t[i] = min(t[2*i], t[2*i+1]);
	}
	int query(int l, int r) {
		l+=n,r+=n+1;
		int ans = 2e9;
		for(;l<r;l>>=1,r>>=1) {
			if(l&1)ans = min(ans, t[l++]);
			if(r&1)ans = min(ans, t[--r]);
		}
		return ans;
	}
};
vector<int> H;
ST st;
ST2 st2;
int pref[N+1];
int build(int l, int r) {
	if(r < l)return -1;
	int p = st.query(l, r);
	L[p] = build(l, p-1);
	R[p] = build(p+1, r);
	mn[p] = H[p];
	if(L[p]!=-1)mn[p] = min(mn[p], mn[L[p]]);
	if(R[p]!=-1)mn[p] = min(mn[p], mn[R[p]]);
	return p;
}
void init(int n, std::vector<int> h) {
	st = ST(h);
	st2 = ST2(h);
	H = h;
	root = build(0, n-1);
	for(int i = 0;i<n;i++) {
		if(i)pref[i] += pref[i-1];
		if(L[i] == -1 and R[i] == -1) {
			pref[i]++;
		}
	}
}


int query(int v, int l, int r, int MX, int D) {
	if(l > r)return 0;
	if(v == -1)return 0;
	if(v > r) {
		return query(L[v], l, r, MX, D);
	}
	if(v < l)
		return query(R[v], l, r, MX, D);
	int ans = 0;	
	if(st2.query(l, r) <= MX)ans=1;
	ans = max(ans, query(L[v], l, v-1, H[v]-D, D)+query(R[v], v+1, r, H[v]-D, D));
	return ans;
}
int max_towers(int l, int r, int D) {
	if(D == 1) return pref[r] - (l?pref[l-1]:0);
  return query(root, l, r, 2e9, D);
}

• Subtask 1: 0 / 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