Submission #741425

#	Time	Username	Problem	Language	Result	Execution time	Memory
741425		GusterGoose27	Radio Towers (IOI22_towers)	C++17	14 / 100	1615 ms	134136 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

typedef array<int, 2> pii;

const int MAXN = 1e5;
const int inf = 1e9;
int height[MAXN];
int n;

class path {
public:
	bool tp; // tp = 0 is >= 2, tp = 1 is single
	pii minmax; // tp = 1
	pii lft; // out in, tp = 0
	pii rt; // out in, tp = 0
	int len; // both
	bool par; // 0 is low, 1 is high, tp = 0
	int d;
	path() {}
	path(int i) {
		d = 0;
		tp = 1;
		minmax = pii{height[i], height[i]};
		len = 1;
		par = 0;
	}
	void reverse() {
		swap(lft, rt);
		par ^= (len&1)^1;
	}
	path(path &l, path &r, int d) : d(d) {
		if (l.tp && r.tp) {
			if (l.minmax[1] >= r.minmax[0]+d) {
				lft = pii{l.minmax[1], r.minmax[0]};
				rt = pii{r.minmax[0], l.minmax[1]};
				len = 2;
				par = 1;
				tp = 0;
				return;
			}
			if (l.minmax[0] <= r.minmax[1]-d) {
				lft = pii{l.minmax[0], r.minmax[1]};
				rt = pii{r.minmax[1], l.minmax[0]};
				len = 2;
				par = 0;
				tp = 0;
				return;
			}
			tp = 1;
			minmax = pii{min(l.minmax[0], r.minmax[0]), max(l.minmax[1], r.minmax[1])};
			len = 1;
			return;
		}
		tp = 0;
		bool rev = 0;
		if (l.tp && !r.tp) {
			rev = 1;
			l.reverse();
			r.reverse();
			swap(l, r);
		}
		if (!l.tp && r.tp) {
			bool rhigh = l.par^(l.len&1)^1; // 0 is mn, 1 is high
			if (rhigh && l.rt[0] >= r.minmax[0]+d) {
				lft = l.lft;
				rt = pii{r.minmax[0], l.rt[0]};
				par = l.par;
				len = l.len+1;
			}
			else if (!rhigh && l.rt[0]+d <= r.minmax[1]) {
				lft = l.lft;
				rt = pii{r.minmax[1], l.rt[0]};
				par = l.par;
				len = l.len+1;
			}
			else if (rhigh && l.rt[0] < r.minmax[1]) {
				rt = pii{r.minmax[1], l.rt[1]};
				par = l.par;
				len = l.len;
				if (len > 2) lft = l.lft;
				else lft = pii{l.rt[1], r.minmax[1]};
			}
			else if (!rhigh && l.rt[0] > r.minmax[0]) {
				rt = pii{r.minmax[0], l.rt[1]};
				par = l.par;
				len = l.len;
				if (len > 2) lft = l.lft;
				else lft = pii{l.rt[1], r.minmax[0]};
			}
			else {
				rt = l.rt;
				lft = l.lft;
				len = l.len;
				par = l.par;
			}
			if (rev) {
				swap(l, r);
				l.reverse();
				r.reverse();
				reverse();
			}
			return;
		}
		par = l.par;
		bool lhigh = l.par^(l.len&1)^1;
		bool rhigh = r.par;
		if (lhigh != rhigh) {
			if ((lhigh && l.rt[0] >= d+r.lft[0]) || (!lhigh && l.rt[0]+d <= r.lft[0])) {
				lft = l.lft;
				rt = r.rt;
				len = l.len+r.len;
				return;
			}
			len = l.len+r.len-2;
			if (l.len > 2) lft = l.lft;
			else lft = pii{l.rt[1], r.lft[1]};
			if (r.len > 2) rt = r.rt;
			else rt = pii{r.lft[1], l.rt[1]};
			return;
		}
		len = l.len+r.len-1;
		if ((lhigh && l.rt[0] > r.lft[0]) || (!lhigh && l.rt[0] < r.lft[0])) {
			lft = l.lft;
			if (r.len > 2) rt = r.rt;
			else rt = pii{r.lft[1], l.rt[0]};
			return;
		}
		if (l.len > 2) lft = l.lft;
		else lft = pii{l.rt[1], r.lft[0]};
		rt = r.rt;
	}
};

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	vector<path> paths;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
			int pos[2]; pos[0] = pos[1] = 0;
			for (int i = rp-lp+1; i > 0; i--) {
				bool cand;
				path cur_path;
				bool mx_reached = 0;
				do {
					if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) {
						mx_reached = 1;
						break;
					}
					cand = (r->get_cost(pos[1]) < l->get_cost(pos[0]));
					pos[cand]++;
					int d = max(r->get_cost(pos[1]), l->get_cost(pos[0]));
					cur_path = path(l->paths[pos[0]], r->paths[pos[1]], d);
				} while (cur_path.len > i); // fix inf condition
				if (!mx_reached) pos[cand]--;
				int mn = max(l->get_cost(pos[0]-1), r->get_cost(pos[1]-1));
				int mx = min(l->get_cost(pos[0]), r->get_cost(pos[1]));
				while (mx > mn+1) {
					int cur = (mn+mx)/2;
					cur_path = path(l->paths[pos[0]], r->paths[pos[1]], cur);
					if (cur_path.len > i) mn = cur;
					else mx = cur;
				}
				if (mx == min(l->get_cost(pos[0]), r->get_cost(pos[1]))) {
					if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) break;
					pos[cand]++;
				}
				paths.push_back(path(l->paths[pos[0]], r->paths[pos[1]], mx));
				i = paths.back().len;
			}
		}
		else {
			paths.push_back(path(lp));
		}
	}
	int get_cost(int p) {
		if (p == paths.size()-1) return inf;
		return paths[p+1].d;
	}
	path* query(int lv, int rv, int d) {
		if (lp > rv || rp < lv) return nullptr;
		if (lp >= lv && rp <= rv) {
			int mn = 0;
			int mx = paths.size();
			// cerr << mn << ' ' << mx << endl;
			while (mx > mn+1) {
				int cur = (mn+mx)/2;
				if (paths[cur].d <= d) mn = cur;
				else mx = cur;
			}
			return &paths[mn];
		}
		path *lq = l->query(lv, rv, d);
		path *rq = r->query(lv, rv, d);
		if (lq == nullptr) return rq;
		if (rq == nullptr) return lq;
		return new path(*lq, *rq, d);
	}
};

stree *tree;

void init(int nn, vector<int> hn) {
	n = nn;
	for (int i = 0; i < n; i++) height[i] = hn[i];
	tree = new stree(0, n-1);
}

int max_towers(int l, int r, int d) {
	path *p = tree->query(l, r, d);
	return (p->len+1-p->par)/2;
}

Compilation message (stderr)

towers.cpp: In constructor 'stree::stree(int, int)':
towers.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |      if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) {
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:157:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |      if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) {
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:176:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |      if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) break;
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:176:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |      if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) break;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp: In member function 'int stree::get_cost(int)':
towers.cpp:188:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |   if (p == paths.size()-1) return inf;
      |       ~~^~~~~~~~~~~~~~~~~
towers.cpp: In constructor 'stree::stree(int, int)':
towers.cpp:177:14: warning: 'cand' may be used uninitialized in this function [-Wmaybe-uninitialized]
  177 |      pos[cand]++;
      |      ~~~~~~~~^

• Subtask 1: 0 / 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