Submission #1082831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082831		Arapak	Radio Towers (IOI22_towers)	C++17	17 / 100	809 ms	25264 KiB

towers

// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "towers.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

#ifdef DEBUG
auto &operator<<(auto &os, const pair<auto, auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto &operator<<(auto &os, const auto &v) {
	os << "{";
	for(auto it=begin(v);it!=end(v);it++) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif

int count_larger(const vi &vec, int x) {
	dbg(vec);
	int b = 0, e = sz(vec);
	while(b < e) {
		int mid = (b+e) / 2;
		if(vec[mid] < x) b = mid + 1;
		else e = mid;
	}
	return sz(vec) - b;
}

struct SegTree {
	int n;
	vector<vi> tree;

	SegTree() {}
	SegTree(vi vals) {
		n = 1;
		while(n < sz(vals))
			n *= 2;
		tree.assign(2*n, {});
		rep(i,0,n)
			if(i < sz(vals))
				tree[n+i] = {vals[i]};
			else
				tree[n+i] = {-1};
		dbg(tree);
		for(int i=n-1;i>0;i--)
			merge(all(tree[2*i]), all(tree[2*i+1]), back_inserter(tree[i]));
		dbg(tree);
	}

	int query(int l, int r, int x) {
		int res = 0;
		for(l+=n, r+=n; l<r; l/=2, r/=2) {
			if(l&1) res += count_larger(tree[l++], x);
			if(r&1) res += count_larger(tree[--r], x);
		}
		return res;
	}
};

const int inf = 2e9 + 7;

int n;
vi h;
vi sel;
vi tim;
vi lft, rht;

SegTree *tree;

void init(int N, vi H) {
	n = N;
	h = H;
	sel.assign(n, 0);
	int prev = -1;
	bool small = false;
	rep(i,0,n) {
		if(small) {
			if(prev != -1 && h[i] <= h[prev]) {
				sel[prev] = false;
				sel[i] = true;
				prev = i;
			}
			else {
				prev = i;
				sel[i] = true;
				small = false;
			}
		} else {
			if(prev != -1 && h[i] >= h[prev]) {
				sel[prev] = false;
				sel[i] = true;
				prev = i;
			}
			else {
				prev = i;
				sel[i] = true;
				small = true;
			}
		}
	}
	dbg(sel);
	set<pii> s;
	tim.assign(n, -1);
	lft.assign(n, -1);
	rht.assign(n, -1);
	prev = -1;
	rep(i,0,n) {
		if(!sel[i])
			continue;
		lft[i] = prev;
		if(prev != -1) rht[prev] = i;
		prev = i;
	}
	auto distance = [&](const int a, const int b) {
		return (int)abs(h[a] - h[b]);
	};
	auto update = [&](const int i) {
		s.erase({tim[i], i});
		tim[i] = inf;
		if(lft[i] != -1) tim[i] = min(tim[i], distance(i, lft[i]));
		if(rht[i] != -1 && rht[rht[i]] != -1) tim[i] = min(tim[i], distance(i, rht[i]));
		s.insert({tim[i], i});
	};
	int parity = 1;
	rep(i,0,n) {
		if(!sel[i])
			continue;
		if(parity) update(i);
		parity ^= 1;
	}
	while(sz(s)) {
		auto [t, i] = *s.begin();
		s.erase(s.begin());
		dbg(t, i);
		if(lft[i] != -1 && t == distance(i, lft[i]) && lft[lft[i]] != -1) {
			rht[lft[lft[i]]] = rht[i];
			update(lft[lft[i]]);
		}
		if(rht[i] != -1 && t == distance(i, rht[i]) && rht[rht[i]] != -1) {
			lft[rht[rht[i]]] = lft[i];
			update(rht[rht[i]]);
		}
		dbg(tim);
	}
	tree = new SegTree(tim);
}

int max_towers(int L, int R, int D) {
	int num = tree->query(0, n, D);
	if(num == 0) return 1;
	dbg(D, num);
	return num;
	// return (num + 1) / 2;
}

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