Submission #827139

#	Time	Username	Problem	Language	Result	Execution time	Memory
827139		rainboy	Floppy (RMI20_floppy)	C++17	100 / 100	77 ms	17152 KiB

floppy

#include "floppy.h"
#include <functional>

using namespace std;

typedef vector<int> vi;

void read_array(int subtask_id, const vi &aa) {
	const int N = 40000;
	int qu[N];
	int n = aa.size();
	string cc(n * 2, 0);
	int cnt = 0, h = 0;
	for (int i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] <= aa[i])
			cc[h++] = '1', cnt--;
		cc[h++] = '0', qu[cnt++] = i;
	}
	while (cnt)
		cc[h++] = '1', cnt--;
	save_to_floppy(cc);
}

vi solve_queries(int subtask_id, int n, const string &cc, const vi &ii, const vi &jj) {
	const int N = 40000;
	int qu[N], ll[N], rr[N];
	int *ej[N], eo[N];
	function<void(int, int)> append = [&](int i, int j) {
		int o = eo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ej[i][o] = j;
	};
	int dd[N], pp[N], qq[N];
	function<int(int, int, int)> dfs1 = [&](int p, int i, int d) {
		dd[i] = d, pp[i] = p;
		int s = 1, k_ = 0, j_ = -1;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p) {
				int k = dfs1(i, j, d + 1);
				s += k;
				if (k_ < k)
					k_ = k, j_ = j;
			}
		}
		qq[i] = j_;
		return s;
	};
	function<void(int, int, int)> dfs2 = [&](int p, int i, int q) {
		int j_ = qq[i]; qq[i] = q;
		if (j_ != -1)
			dfs2(i, j_, q);
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p && j != j_)
				dfs2(i, j, j);
		}
	};
	function<int(int, int)> lca = [&](int i, int j) {
		while (qq[i] != qq[j])
			if (dd[qq[i]] > dd[qq[j]])
				i = pp[qq[i]];
			else
				j = pp[qq[j]];
		return dd[i] < dd[j] ? i : j;
	};
	int cnt = 0;
	for (int h = 0, i = 0; h < n * 2; h++)
		if (cc[h] == '0')
			ll[i] = cnt == 0 ? -1 : qu[cnt - 1], qu[cnt++] = i++;
		else
			rr[qu[--cnt]] = i;
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	int r = -1;
	for (int i = 0; i < n; i++)
		if (ll[i] == -1 && rr[i] == n)
			r = i;
		else if (ll[i] != -1 && rr[ll[i]] <= rr[i])
			append(ll[i], i);
		else
			append(rr[i], i);
	dfs1(-1, r, 0);
	dfs2(-1, r, r);
	int q = ii.size();
	vi ans(q, 0);
	for (int h = 0; h < q; h++)
		ans[h] = lca(ii[h], jj[h]);
	for (int i = 0; i < n; i++)
		free(ej[i]);
	return ans;
}

Compilation message (stderr)

floppy.cpp: In lambda function:
floppy.cpp:30:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |   if (o >= 2 && (o & o - 1) == 0)
      |                      ~~^~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72