Submission #632810

#	Time	Username	Problem	Language	Result	Execution time	Memory
632810		study	Radio Towers (IOI22_towers)	C++17	0 / 100	4099 ms	18400 KiB

towers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using indexed_set = tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;

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

struct item{
	int l,r,nb;
};

struct comp{
	int min,max,diff;
};

comp diffl[400010], diffr[400010];

item query(int l, int r, int L, int R){
	l += half;
	r += half;
	item ans = item{INT_MAX,0,0};
	while (l <= r){
		if (l&1){
			int idx1 = segt[l].order_of_key(L);
			int idx2 = segt[l].order_of_key(R+1)-1;
			ans.nb += max(0,idx2-idx1);
			ans.r = max(ans.r,*segt[l].find_by_order(idx2));
			ans.l = min(ans.l,*segt[l].find_by_order(idx1));
			l++;
		}
		if (r%2 == 0){
			int idx1 = segt[r].order_of_key(L);
			int idx2 = segt[r].order_of_key(R+1)-1;
			ans.nb += max(0,idx2-idx1);
			ans.r = max(ans.r,*segt[r].find_by_order(idx2));
			ans.l = min(ans.l,*segt[r].find_by_order(idx1));
			r--;
		}
		l >>= 1;
		r >>= 1;
	}
	return ans;
}

void add(int node, int val){
	node += half;
	segt[node].insert(val);
	node >>= 1;
	while (node){
		segt[node].insert(val);
		node >>= 1;
	}
}

void modify(int idx, int val){
	idx += n;
	idx >>= 1;
	maxi[idx] = val;
	while (idx){
		maxi[idx] = max(maxi[2*idx],maxi[2*idx+1]);
		idx >>= 1;
	}
}

int max_query(int l, int r){
	l += n;
	r += n;
	int ans = 0;
	while (l <= r){
		if (l&1){
			ans = max(ans,maxi[l]);
			l++;
		}
		if (r%2 == 0){
			ans = max(ans,maxi[r]);
			r--;
		}
	}
	return ans;
}

void build_left(int idx, int l, int r){
	if (l == r){
		diffl[idx] = comp{a[l],a[l],0};
		return;
	}
	int mid = (l+r)/2;
	build_left(2*idx,l,mid);
	build_left(2*idx+1,mid+1,r);
	diffl[idx].max = max(diffl[2*idx].max,diffl[2*idx+1].max);
	diffl[idx].min = min(diffl[2*idx].min,diffl[2*idx+1].min);
	diffl[idx].diff = max({diffl[2*idx].diff,diffl[2*idx+1].diff,diffl[2*idx+1].max-diffl[2*idx].min});
}

void build_right(int idx, int l, int r){
   if (l == r){
      diffr[idx] = comp{a[l],a[l],0};
      return;
   }
   int mid = (l+r)/2;
   build_right(2*idx,l,mid);
   build_right(2*idx+1,mid+1,r);
   diffr[idx].max = max(diffr[2*idx].max,diffr[2*idx+1].max);
   diffr[idx].min = min(diffr[2*idx].min,diffr[2*idx+1].min);
   diffr[idx].diff = max({diffr[2*idx].diff,diffr[2*idx+1].diff,diffr[2*idx].max-diffr[2*idx+1].min});

}

int query_left(int idx, int l, int r, int L, int R){
	if (r < L or l > R) return -1;
	if (l >= L and r <= R) return diffl[idx].diff;
	int mid = (l+r)/2;
	return max(query_left(2*idx,l,mid,L,R),query_left(2*idx+1,mid+1,r,L,R));
}

int query_right(int idx, int l, int r, int L, int R){
	if (r < L or l > R) return -1;
	if (l >= L and r <= R) return diffr[idx].diff;
	int mid = (l+r)/2;
	return max(query_right(2*idx,l,mid,L,R),query_right(2*idx+1,mid+1,r,L,R));
}

void init(int N, vector<int> H){
	n = N;
	vector<pair<int,int>> v,deltas;
	for (int i=0; i<n; ++i){
		v.emplace_back(H[i],i);
		a[i] = H[i];
		modify(i,a[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,max_query(i.second,A));
		}
		if (B != INT_MIN){
			if (B == i.second-1) ok = true;
			maxi = min(maxi,max_query(B,i.second));
		}
		if (maxi != i.first and !ok){
			if (maxi == INT_MAX){
				possibleDeltas.emplace_back(maxi);
				deltas.emplace_back(maxi,i.second);
			}
			else{
				possibleDeltas.emplace_back(maxi-i.first);
				deltas.emplace_back(maxi-i.first,i.second);
			}
			possibleDeltas.emplace_back(maxi);
		}
		pos.emplace(i.second);
	}
	possibleDeltas.emplace_back(INT_MAX);
	sort(possibleDeltas.begin(),possibleDeltas.end());
	possibleDeltas.erase(unique(possibleDeltas.begin(),possibleDeltas.end()),possibleDeltas.end());
	for (auto i:deltas){
		int idx = lower_bound(possibleDeltas.begin(),possibleDeltas.end(),i.first)-possibleDeltas.begin();
		add(idx,i.second);
	}
	for (int i=0; i<possibleDeltas.size(); ++i){
		add(i,INT_MAX);
		add(i,INT_MIN);
	}
	build_left(1,0,n-1);
	build_right(1,0,n-1);
}

int max_towers(int L, int R, int D){
	int from = lower_bound(possibleDeltas.begin(),possibleDeltas.end(),D)-possibleDeltas.begin();
	item res = query(from,possibleDeltas.size()-1,L,R);
	int deb = L, fin = res.l-1, ansL = -1;
	while (deb <= fin){
		int mid = (deb+fin)/2;
		if (max_query(mid,res.l)-a[res.l] >= D){
			deb = mid+1;
			ansL = mid;
		}
		else fin = mid-1;
	}
	bool has1 = 0, has2 = 0;
	if (query_left(1,0,n-1,L,ansL) >= D) has1 = true;
	deb = res.r+1, fin = R;
	int ansR = -1;
	while (deb <= fin){
		int mid = (deb+fin)/2;
		if (max_query(res.r,mid)-a[res.r] >= D){
			fin = mid-1;
			ansR = mid;
		}
		else deb = mid+1;
	}
	if (query_right(1,0,n-1,res.r,R) >= D) has2 = true;
	return res.nb+has1+has2;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:173:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |  for (int i=0; i<possibleDeltas.size(); ++i){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:196:6: warning: variable 'ansR' set but not used [-Wunused-but-set-variable]
  196 |  int ansR = -1;
      |      ^~~~

• 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