Submission #762327

#	Time	Username	Problem	Language	Result	Execution time	Memory
762327		amunduzbaev	Radio Towers (IOI22_towers)	C++17	56 / 100	789 ms	9032 KiB

towers

#include "towers.h"

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

#ifndef EVAL
#include "stub.cpp"
#endif

const int N = 1e5 + 5;
int first, mount;
vector<int> a, l, r, res;

struct ST{
	vector<int> tree;
	int N;
	
	ST(int N): N(N){
		tree.resize(N << 2);
	}
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx){
			tree[x] = v;
			return;
		}
		
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l){
			return -(N << 2);
		}
		if(lx >= l && rx <= r){
			return tree[x];
		}
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}Max(N), Min(N);

void init(int n, vector<int> H) {
	first = 1;
	a = H;
	vector<int> pos_mnt;
	for(int i=0;i<n;i++){
		int is = 0;
		if(!i || a[i] > a[i - 1]) is++;
		if(i + 1 == n || a[i] > a[i + 1]) is++;
		if(is){
			pos_mnt.push_back(i);
		}
	}
	
	if((int)pos_mnt.size() == 1) mount = pos_mnt[0] + 1;
	l.resize(n), r.resize(n);
	
	ST Max(n), Min(n);
}

int max_towers(int l_, int r_, int d) {
	if(mount){
		int p = mount - 1;
		if(l_ <  p && p <  r_ && a[l_] + d <= a[p] && a[r_] + d <= a[p]){
			return 2;
		}
		
		return 1;
	}
	if(first){
		int n = a.size();
		vector<int> ss;
		for(int i=0;i<n;i++){
			while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
			int l_ = 0, r_ = ss.size();
			while(l_ < r_){
				int m = (l_ + r_) >> 1;
				if(a[ss[m]] >= a[i] + d) l_ = m + 1;
				else r_ = m;
			}
			l[i] = 0;
			if(l_) l[i] = ss[l_ - 1] + 1;
			ss.push_back(i);
		}
		
		ss.clear();
		for(int i=n-1;~i;i--){
			while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
			int l_ = 0, r_ = ss.size();
			while(l_ < r_){
				int m = (l_ + r_) >> 1;
				if(a[ss[m]] >= a[i] + d) l_ = m + 1;
				else r_ = m;
			}
			
			r[i] = n - 1;
			if(l_)  r[i] = ss[l_ - 1] - 1;
			ss.push_back(i);
		}
		
		vector<int> p(n);
		iota(p.begin(), p.end(), 0);
		sort(p.begin(), p.end(), [&](int i, int j){
			if(r[i] != r[j]) return r[i] < r[j];
			if(l[i] != l[j]) return l[i] > l[j];
			return a[i] < a[j];
		});
		
		int mxL = -1;
		for(auto i : p){
			if(l[i] <= mxL){
				continue;
			}
			mxL = max(mxL, l[i]);
			res.push_back(i);
		}
		
		for(int i=0;i<n;i++){
			Min.set(i, -r[i]);
			Max.set(i, l[i]);
		}
		
		first = 0;
	}
	
	int L = lower_bound(res.begin(), res.end(), l_) - res.begin();
	int R = upper_bound(res.begin(), res.end(), r_) - res.begin() - 1;
	if(L <= R){
		int ans = R - L + 1;
		if(l_ < l[res[L]]){
			if(-Min.get(l_, l[res[L]] - 1) < l[res[L]]){
				ans++;
			}
		}
		if(r[res[R]] < r_){
			if(r[res[R]] < Max.get(r[res[R]] + 1, r_)){
				ans++;
			}
		}
		
		return ans;
	} else {
		int mnR = -Min.get(l_, r_);
		int mxL = Max.get(l_, r_);
		if(mnR < mxL){
			return 2;
		}
		return 1;
	}
	return 0;
}

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