Submission #627638

#	Time	Username	Problem	Language	Result	Execution time	Memory
627638		Noam527	Radio Towers (IOI22_towers)	C++17	18 / 100	1706 ms	76488 KiB

towers

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

struct info {
	int len[2][2];
	info(int x = -1) {
		len[0][0] = len[1][1] = -1e9;
		len[0][1] = len[1][0] = -1e9;
		if (x == 0) {
			len[0][0] = 1;
		}
		if (x == 1) {
			len[1][1] = 1;
		}
	}
	info operator * (const info &a) const {
		info res;
		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) {
		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;
	segtree() {}
	segtree(int sz) {
		tim = 0;
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n, node());
	}
	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) {
		tim++;
		x += n - 1;
		t[x].add(tim, info(val));
		while (x) {
			x = (x - 1) / 2;
			fix(x);
		}
	}
	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);
	}
};

int oldn;
vector<int> oldh;

int n;
vector<int> taken_ind;
vector<int> h;
vector<pair<int, int>> w;

segtree T;

void init(int N, std::vector<int> H) {
	oldn = N;
	oldh = H;
	h = { H[0], H[1] };
	taken_ind = { 0, 1 };
	for (int i = 2; i < oldn; i++) {
		if (abs(h[h.size() - 2] - h.back()) + abs(h.back() - H[i]) == abs(h[h.size() - 2] - H[i]))
			h.pop_back(), taken_ind.pop_back();
		h.push_back(H[i]);
		taken_ind.push_back(i);
	}
	n = h.size();
	
	for (int i = 0; i + 1 < h.size(); i++)
		w.emplace_back(abs(h[i] - h[i + 1]), i);
	if (OO) {
		cout << "w:\n";
		for (const auto &i : w) cout << i.first << " " << i.second << '\n';
	}
	sort(w.rbegin(), w.rend());
	
	T = segtree(n);
	for (auto &i : w) {
		if (h[i.second] < h[i.second + 1])
			T.upd(i.second, 0);
		else
			T.upd(i.second, 1);
	}
}

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(oldh[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) {
	// find time
	int lo = -1, hi = (int)w.size() - 1, mid;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (w[mid].first >= D) lo = mid;
		else hi = mid - 1;
	}
	int tim = lo + 1;

	// fix L, R
	auto it = lower_bound(taken_ind.begin(), taken_ind.end(), L);
	int LL = *it;
	int l = it - taken_ind.begin();
	it = prev(upper_bound(taken_ind.begin(), taken_ind.end(), R));
	int RR = *it;
	int r = it - taken_ind.begin();

	// break into cases - and also don't forget to consider the boundaries
	if (R < LL) {
		// nothing in between - this is a monotonic range
		return 1;
	}
	// there's something in between: l <= r
	if (OO) {
		cout << "data until now:\n";
		cout << "taken_ind: ";
		for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
		cout << "l LL " << l << " " << LL << '\n';
		cout << "r RR " << r << " " << RR << '\n';
		cout << "tim " << tim << '\n';
	}
	info q = T.query(l, r - 1, tim);
	if (OO) {
		cout << "from query received:\n";
		q.print();
	}
	if (L < LL) {
		// consider left boundary
		info boundary = info();
		if (oldh[L] + D <= oldh[LL])
			boundary = info(0);
		else if (oldh[L] - D >= oldh[LL])
			boundary = info(1);
		q = boundary * q;
	}
	if (RR < R) {
		// consider right boundary
		info boundary = info();
		if (oldh[RR] + D <= oldh[R])
			boundary = info(0);
		else if (oldh[RR] - D >= oldh[R])
			boundary = info(1);
		q = q * boundary;
	}
	return max(1, max(q.len[0][0], q.len[0][1]) / 2 + 1);
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i = 0; i + 1 < h.size(); i++)
      |                  ~~~~~~^~~~~~~~~~
towers.cpp: In function 'int bruteforce(int, int, int)':
towers.cpp:140:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for (int i = 0; i + 1 < val.size(); i++) {
      |                   ~~~~~~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:177:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  177 |   for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
      |   ^~~
towers.cpp:177:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  177 |   for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
      |                                                     ^~~~

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