Submission #1082806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082806		Arapak	Radio Towers (IOI22_towers)	C++17	0 / 100	537 ms	24356 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;

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;
			}
		}
	}
	tim.assign(n, inf);
	prev = -1;
	rep(i,0,n) {
		if(!sel[i]) {
			tim[i] = -1;
			continue;
		}
		if(prev != -1) {
			tim[prev] = min(tim[prev], (int)abs(h[prev] - h[i]));
			tim[i] = min(tim[i], (int)abs(h[prev] - h[i]));
		}
		prev = i;
	}
	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 + 1) / 2;
}

• 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