Submission #1082260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082260		s_tree	Radio Towers (IOI22_towers)	C++17	37 / 100	4038 ms	12932 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<vector<int>>&h) {
		n  = h.size();
		t.resize(2*n);
		for(int i = 0;i<n;i++){
			t[i+n]=h[i];
			sort(t[i+n].begin(), t[i+n].end());
		}
		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) {
		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);
	for(int i = 0;i<n;i++) {
		bool check=1;
		if(i and H[i-1] < H[i])check=false;
		if(i+1 < n and H[i+1] < H[i])check=false;
		if(i)pref[i] =pref[i-1];
		pref[i]+=check;
	}
}


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 query2(int v, int l, int r) {
	if(l > r)return 0;
	if(v == -1)return 0;
	if(v>r)return query2(L[v], l, r);
	if(v<l)return query2(R[v], l, r);
	int ans=0;
	if(L[v] < l and (R[v] == -1 or R[v] > r))return 1;
	ans+=query2(L[v], l, r);
	ans+=query2(R[v], l, r);
	return ans;
}
int max_towers(int l, int r, int D) {
	if(D == 1) {
		if(l == r)return 1;
		if(l + 1 == r)return 1;
		int ans = pref[r-1]-pref[l];
		if(r and H[r-1] > H[r])ans++;
		if(l+1<H.size() and H[l+1] > H[l])ans++;
		return ans;
	}

  return query(root, l, r, 2e9, D);
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:140:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   if(l+1<H.size() and H[l+1] > H[l])ans++;
      |      ~~~^~~~~~~~~

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