Submission #1082248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082248		s_tree	Radio Towers (IOI22_towers)	C++17	0 / 100	4088 ms	21824 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;
	}
};
struct ST3 {
	vector<vector<int>> t;
	int n;
	ST3(){}
	ST3(vector<int>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++)t[i+n].push_back(h[i]);
		for(int i = n-1;i>0;i--){
				merge(t[2*i].begin(), t[2*i].end(), t[2*i+1].begin(), t[2*i+1].end(), back_inserter(t[i]));
		}
	}
	int query(int l, int r) {
		int key = r;
		l+=n,r+=n+1;
		int ans=0;
		for(;l<r;l>>=1,r>>=1) {
			if(l&1) {
				ans+=upper_bound(t[l].begin(), t[l].end(), key) - t[l].begin();
				l++;
			}
			if(r&1) {
				--r;
				ans+=upper_bound(t[r].begin(), t[r].end(), key) - t[r].begin();
			}
		}
		return ans;
	}
};
vector<int> H;
ST st;
ST2 st2;
ST3 st3;
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);
	vector<int> tt(n, n+10);
	for(int i = 0;i<n;i++) {
		if(L[i] != -1 and R[i] != -1) {
			tt[L[i]] = R[i];
		}
	}
	st3 = ST3(tt);
}


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 st3.query(l, r)+1;
  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