Submission #627819

#	Time	Username	Problem	Language	Result	Execution time	Memory
627819		Noam527	Radio Towers (IOI22_towers)	C++17	0 / 100	713 ms	148388 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
typedef long long ll;
using namespace std;

struct info {
	int len[2][2];
	int l, r;
	info(int x = -1, int i = 0) {
		len[0][0] = len[1][1] = -1e9;
		len[0][1] = len[1][0] = -1e9;
		l = 1e9, r = -1e9;
		if (x == 0) {
			l = r = i;
			len[0][0] = 1;
		}
		if (x == 1) {
			l = r = i;
			len[1][1] = 1;
		}
	}
	info operator * (const info &a) const {
		info res;
		res.l = min(l, a.l);
		res.r = max(r, a.r);
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
			res.len[i][j] = max(max(res.len[i][j], len[i][j]), a.len[i][j]);
		}
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
			res.len[i][k] = max(res.len[i][k], len[i][j] + a.len[1 ^ j][k]);
		}
		return res;
	}
	void print() {
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
			cout << i << " -> " << j << ": " << len[i][j] << '\n';
		}
	}
};
struct node {
	vector<pair<int, info>> data;
	node() {
		data.emplace_back(0, info());
	}
	void add(int tim, info i) {
		if (data.size() && data.back().first == tim)
			data.back().second = i;
		else
			data.emplace_back(tim, i);
	}
	info& get(int tim) {
		tim = max(tim, 0);
		int lo = 0, hi = (int)data.size() - 1, mid;
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (data[mid].first <= tim) lo = mid;
			else hi = mid - 1;
		}
		return data[lo].second;
	}
};

struct segtree {
	int n;
	int tim;
	vector<node> t;
	vector<pair<int, int>> range;
	segtree() {}
	segtree(int sz) {
		tim = 0;
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n, node());
	}
	void advance_time(int newtim) {
		tim = max(tim, newtim);
	}
	void fix(int x) {
		t[x].add(tim, t[2 * x + 1].get(tim) * t[2 * x + 2].get(tim));
	}
	void upd(int x, int val) {
		if (OO) cout << "upd " << x << " " << val << '\n';
		x += n - 1;
		t[x].add(tim, info(val, x - (n - 1)));
		while (x) {
			x = (x - 1) / 2;
			fix(x);
		}
	}
	int is_alive(int i, int T) {
		info tmp = t[i + n - 1].get(T);
		if (tmp.len[0][0] == 1 || tmp.len[1][1] == 1) return 1;
		return 0;
	}
	info query(int l, int r, int T) {
		if (l > r) return info();
		return query(l, r, T, 0, 0, n - 1);
	}
	info query(int l, int r, int T, int node, int nl, int nr) {
		if (nr < l || r < nl) return info();
		if (l <= nl && nr <= r) return t[node].get(T);
		int mid = (nl + nr) / 2;
		return query(l, r, T, 2 * node + 1, nl, mid) * query(l, r, T, 2 * node + 2, mid + 1, nr);
	}
};

struct sptable {
	int n;
	vector<int> a;
	vector<int> mn, mx;
	sptable() {}
	sptable(const vector<int> &b) {
		a = b;
		n = max(2, (int)a.size());
		while (n != (n & -n)) n += (n & -n);
		mn.resize(2 * n);
		mx.resize(2 * n);
		for (int i = 0; i < a.size(); i++)
			mn[i + n - 1] = mx[i + n - 1] = a[i];
		for (int i = n - 2; i >= 0; i--)
			mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]), mx[i] = max(mx[2 * i + 1], mx[2 * i + 2]);
	}
	pair<int, int> query(int l, int r) {
		if (l > r) return{ 1e9, -1e9 };
		int mnres = 1e9, mxres = -1e9;
		for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
			if (!(l & 1)) {
				mnres = min(mnres, mn[l]);
				mxres = max(mxres, mx[l]);
				l++;
			}
			if (r & 1) {
				mnres = min(mnres, mn[r]);
				mxres = max(mxres, mx[r]);
				r--;
			}
		}
		if (l == r) {
			mnres = min(mnres, mn[l]);
			mxres = max(mxres, mx[l]);
		}
		return{ mnres, mxres };
	}
};

struct superset {
	int n;
	vector<int> a;
	set<int> ind;
	set<pair<int, int>> q;
	superset() {}
	superset(const vector<int> &b) {
		a = b;
		n = a.size();
		for (int i = 0; i < n; i++)
			ind.insert(i);
		for (int i = 0; i < n; i++)
			q.emplace(abs(a[i] - a[i + 1]), i);
	}
	set<pair<int, int>>::iterator getq_element(set<int>::iterator it) {
		// assuming it exists
		return q.lower_bound(pair<int, int>(abs(a[*it] - a[*next(it)]), *it));
	}
	int upto(int R) {
		auto it = ind.upper_bound(R);
		if (it == ind.begin()) return -1;
		return *prev(it);
	}
	int atleast(int L) {
		auto it = ind.lower_bound(L);
		if (it == ind.end()) return 1e9;
		return *it;
	}
	// data kept between exchanges
	int last_min;
	set<int>::iterator last_i, last_j, last_k;

	int size() {
		return ind.size();
	}
	int get_min() {
		return last_min = q.begin()->first;
	}
	void get_triple() {
		auto p = *q.begin();
		auto it = ind.lower_bound(p.second);
		if (it == ind.begin())
			last_i = it;
		else
			last_i = prev(it);
		last_j = next(last_i);
		last_k = next(last_j);
	}
	void remove(int &removed_index, int &i, int &j) {
		int mx = max(max(a[*last_i], a[*last_j]), a[*last_k]);
		int mn = min(min(a[*last_i], a[*last_j]), a[*last_k]);
		int median = (ll)a[*last_i] + (ll)a[*last_j] + (ll)a[*last_k] - mn - mx;
		set<int>::iterator it;
		if (median == a[*last_i]) it = last_i;
		else if (median == a[*last_j]) it = last_j;
		else it = last_k;

		removed_index = *it;
		if (it == ind.begin()) i = -1;
		else i = *prev(it);
		if (next(it) == ind.end()) j = -1;
		else j = *next(it);

		// update q
		if (i == -1) {
			q.erase(getq_element(it));
		}
		else if (j == -1) {
			q.erase(getq_element(prev(it)));
		}
		else {
			q.erase(getq_element(prev(it)));
			q.erase(getq_element(it));
			q.insert(pair<int, int>(abs(a[i] - a[j]), i));
		}
		// update ind
		ind.erase(it);
	}
};

int n;
vector<int> h;
superset ind;

segtree T;
sptable table;

void init(int N, std::vector<int> H) {
	n = N;
	h = H;
	ind = superset(h);
	
	T = segtree(n);
	table = sptable(h);
	for (int i = 0; i + 1 < n; i++)
		if (h[i] < h[i + 1])
			T.upd(i, 0);
		else
			T.upd(i, 1);
	while (ind.size() > 2) {
		int d = ind.get_min();

		T.advance_time(d);
		ind.get_triple();
		int index, li, ri;
		ind.remove(index, li, ri);
		T.upd(index, -1);
		if (li != -1) {
			if (ri == -1) {
				T.upd(li, -1);
			}
			else {
				if (h[li] < h[ri])
					T.upd(li, 0);
				else
					T.upd(li, 1);
			}
		}
		if (OO) {
			cout << "at d = " << d << ", remove li ri " << index << " " << li << " " << ri << '\n';
		}
	}
}

int bruteforce(int l, int r, int d) {
	int len = r - l + 1;
	int best = 0;
	for (int mask = 0; mask < (1 << len); mask++) {
		vector<int> val;
		for (int i = l; i <= r; i++) {
			if (mask & (1 << (i - l)))
				val.push_back(h[i]);
		}
		if (val.size() % 2 == 0) continue;
		bool good = true;
		for (int i = 0; i + 1 < val.size(); i++) {
			if (i % 2 == 0 && val[i] + d > val[i + 1]) good = false;
			if (i % 2 == 1 && val[i] - d < val[i + 1]) good = false;
		}
		if (good)
			best = max(best, (int)val.size() / 2 + 1);
	}
	return best;
}

int max_towers(int L, int R, int D) {
	int tim = D - 1;

	// fix L, R
	info q = T.query(L, R, tim);
	int l = q.l;
	int r = q.r;
	if (OO) {
		cout << "l r " << l << " " << r << '\n';
	}

	// break into cases - and also don't forget to consider the boundaries
	if (r < l) {
		// nothing in between - this is a monotonic range
		return 1;
	}
	q = T.query(l, r - 1, tim);
	if (OO) {
		cout << "from query received:\n";
		q.print();
	}
	if (L < l) {
		// consider left boundary
		info boundary = info();
		auto pa = table.query(L, l - 1);
		if (pa.first + D <= h[l])
			boundary = info(0);
		else if (pa.second - D >= h[l])
			boundary = info(1);
		q = boundary * q;
	}
	if (r < R) {
		// consider right boundary
		info boundary = info();
		auto pa = table.query(r + 1, R);
		if (h[r] - D >= pa.first)
			boundary = info(1);
		else if (h[r] + D <= pa.second)
			boundary = info(0);
		q = q * boundary;
	}
	return max(1, q.len[0][1] / 2 + 1);
}

Compilation message (stderr)

towers.cpp: In constructor 'sptable::sptable(const std::vector<int>&)':
towers.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for (int i = 0; i < a.size(); i++)
      |                   ~~^~~~~~~~~~
towers.cpp: In function 'int bruteforce(int, int, int)':
towers.cpp:282:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  282 |   for (int i = 0; i + 1 < val.size(); i++) {
      |                   ~~~~~~^~~~~~~~~~~~

• 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