Submission #763574

#	Time	Username	Problem	Language	Result	Execution time	Memory
763574		amunduzbaev	Radio Towers (IOI22_towers)	C++17	100 / 100	1604 ms	144620 KiB

towers

#include "towers.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#ifndef EVAL
#include "stub.cpp"
#endif
 
#define ar array
typedef int64_t ll;
//~ #define int ll
 
const int inf = 1e9 + 7;
const int N = 1e5 + 5;
const int B = 320;
//~ int first, mount;
//~ vector<int> a, l, r, res;
vector<ar<int, 2>> res;
vector<int> a, tot;
 
struct STMx{
	vector<int> tree;
	int N;
	
	STMx(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 0;
		}
		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);
	}
	
	int first(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(tree[x] < v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(tree[x << 1] >= v) return first(l, r, v, lx, m, x << 1);
			else return first(l, r, v, m + 1, rx, x << 1 | 1);
		}
		int m = (lx + rx) >> 1;
		int res = first(l, r, v, lx, m, x << 1);
		if(res == -1) res = first(l, r, v, m + 1, rx, x << 1 | 1);
		return res;
	}
	
	int first(int l, int r, int v){
		return first(l, r, v, 0, N, 1);
	}
	
	int last(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(tree[x] < v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(tree[x << 1 | 1] >= v) return last(l, r, v, m + 1, rx, x << 1 | 1);
			else return last(l, r, v, lx, m, x << 1);
		}
		
		int m = (lx + rx) >> 1;
		int res = last(l, r, v, m + 1, rx, x << 1 | 1);
		if(res == -1) res = last(l, r, v, lx, m, x << 1);
		return res;
	}
	
	int last(int l, int r, int v){
		return last(l, r, v, 0, N, 1);
	}
}Max(N), DMax(N);
     
struct ST{
	vector<int> Max, Min, t01, t10;
	int N;
	
	ST(int N): N(N){
		Max.resize(N << 2);
		Min.resize(N << 2);
		t01.resize(N << 2);
		t10.resize(N << 2);
	}
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx){
			t01[x] = t10[x] = 0;
			Max[x] = Min[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);
		
		t01[x] = max({t01[x << 1], t01[x << 1 | 1], Max[x << 1 | 1] - Min[x << 1]});
		t10[x] = max({t10[x << 1], t10[x << 1 | 1], Max[x << 1] - Min[x << 1 | 1]});
		Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
		Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int mn, mx;
	int get01(int l, int r, int d, int lx, int rx, int x){
		if(lx > r || rx < l){
			return -1;
		}
		if(lx >= l && rx <= r){
			if(t01[x] < d && Max[x] - mn < d){
				mn = min(mn, Min[x]);
				return -1;
			}
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(Max[x << 1] - mn >= d || t01[x << 1] >= d){
				return get01(l, r, d, lx, m, x << 1);
			} else {
				mn = min(mn, Min[x << 1]);
				return get01(l, r, d, m + 1, rx, x << 1 | 1);
			}
		}
		int m = (lx + rx) >> 1;
		int res = get01(l, r, d, lx, m, x << 1);
		if(res == -1) res = get01(l, r, d, m + 1, rx, x << 1 | 1);
		
		return res;
	}
	
	int get01(int l, int r, int d){
		mn = inf;
		return get01(l, r, d, 0, N, 1);
	}
	
	int get10(int l, int r, int d, int lx, int rx, int x){
		if(lx > r || rx < l){
			return -1;
		}
		
		if(lx >= l && rx <= r){
			if(t10[x] < d && Max[x] - mn < d){
				mn = min(mn, Min[x]);
				return -1;
			}
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(Max[x << 1 | 1] - mn >= d || t10[x << 1 | 1] >= d){
				return get10(l, r, d, m + 1, rx, x << 1 | 1);
			} else {
				mn = min(mn, Min[x << 1 | 1]);
				return get10(l, r, d, lx, m, x << 1);
			}
		}
		
		int m = (lx + rx) >> 1;
		int res = get10(l, r, d, m + 1, rx, x << 1 | 1);
		if(res == -1) res = get10(l, r, d, lx, m, x << 1);
		
		return res;
	}
	
	int get10(int l, int r, int d){
		mn = inf;
		return get10(l, r, d, 0, N, 1);
	}
}tree(N);
 
vector<int> v;

int cnt[B][N];
 
struct sqD{
	int a[N];
	
	sqD(){
		memset(cnt, 0, sizeof cnt);
		memset(a, 0, sizeof a);
	}
	
	void set(int i, int v){
		a[i] = v;
		cnt[i / B][a[i]]++;
	}
	
	void build(){
		for(int i=0;i<B;i++){
			for(int j=N-2;~j;j--){
				cnt[i][j] += cnt[i][j + 1];
			}
		}
	}
	
	int get(int l, int r, int d){
		int l_ = l / B, r_ = r / B;
		
		int res = 0;
		for(int j=l_+1;j<r_;j++){
			res += cnt[j][d];
		}
		
		if(l_ == r_){
			for(int i=l;i<=r;i++) res += (a[i] >= d);
		} else {
			for(int i=l;i<(l_ + 1) * B;i++) res += (a[i] >= d);
			for(int i=r_ * B;i <= r;i++) res += (a[i] >= d);
		}
		
		return res;
	}
}block;

void init(int n, vector<int> h) {
	a = h;
	vector<int> pos;
	for(int i=0;i<n;i++){
		Max.set(i, a[i]);
		if((!i || a[i] < a[i - 1]) && (i + 1 == n || a[i] < a[i + 1])){
			pos.push_back(i);
		}
	}
	
	set<int> ss;
	multiset<ar<int, 2>> dif;
	
	for(int i=0;i<(int)pos.size();i++){
		if(i){
			int mx = Max.get(pos[i - 1], pos[i]);
			dif.insert({mx - a[pos[i - 1]], pos[i - 1]});
			dif.insert({mx - a[pos[i]], pos[i]});
		}
		ss.insert(pos[i]);
	}
	
	while(!dif.empty()){
		auto [d, i] = *dif.begin();
		res.push_back({d, i});
		
		//~ cout<<i<<" "<<d<<"\n";
		auto it = ss.lower_bound(i);
		auto R = it; R++;
		if(it == ss.begin() || R == ss.end()){
			if(it == ss.begin()){
				int mx = Max.get(*it, *R);
				dif.erase(dif.find({mx - a[*it], *it}));
				dif.erase(dif.find({mx - a[*R], *R}));
			} else {
				auto L = it; L--;
				int mx = Max.get(*L, *it);
				dif.erase(dif.find({mx - a[*it], *it}));
				dif.erase(dif.find({mx - a[*L], *L}));
			}
			ss.erase(it);
			continue;
		}
		
		auto L = it; --L;
		
		int mx = Max.get(*L, *it);
		dif.erase(dif.find({mx - a[*it], *it}));
		dif.erase(dif.find({mx - a[*L], *L}));
		
		mx = Max.get(*it, *R);
		dif.erase(dif.find({mx - a[*it], *it}));
		dif.erase(dif.find({mx - a[*R], *R}));
		
		mx = Max.get(*L, *R);
		dif.insert({mx - a[*L], *L});
		dif.insert({mx - a[*R], *R});
		
		ss.erase(it);
	}
	res.push_back({inf, *ss.begin()});
	for(auto x : res) tot.push_back(x[0]);
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	v.resize(n);
	
	for(auto [d, i] : res){
		v[i] = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1;
	}
	
	for(int i=0;i<n;i++){
		tree.set(i, a[i]);
		DMax.set(i, v[i]);
		assert(v[i] <= N);
		block.set(i, v[i]);
	}
	
	block.build();
}
 
int max_towers(int l, int r, int d) {
	int D = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1;
	int n = a.size();
	
	auto get = [&](int l, int r, int d){
		int res = 0;
		for(int i=l;i<=r;i++){
			if(v[i] >= d) res++;
		}
		
		return res;
	};
	//~ int res = get(l, r, D);
	int res = block.get(l, r, D);
	
	if(!res){
		int l_ = tree.get01(l, r, d), r_ = tree.get10(l, r, d);
		if(~l_ && ~r_ && l_ <= r_){
			return 2;
		}
		
		return 1;
	}
	
	int l_ = DMax.first(l, r, D), r_ = DMax.last(l, r, D);
	assert(~l_ && ~r_);
	l_ = Max.last(l, l_, a[l_] + d);
	r_ = Max.first(r_, r, a[r_] + d);
	
	if(~l_ && ~tree.get01(l, l_, d)){
		res++;
	}
	if(~r_ && ~tree.get10(r_, r, d)){
		res++;
	}
	
	return res;
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:322:6: warning: unused variable 'n' [-Wunused-variable]
  322 |  int n = a.size();
      |      ^
towers.cpp:324:7: warning: variable 'get' set but not used [-Wunused-but-set-variable]
  324 |  auto get = [&](int l, int r, int d){
      |       ^~~

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