Submission #494498

#	Time	Username	Problem	Language	Result	Execution time	Memory
494498		gesix56151	Floppy (RMI20_floppy)	C++14	0 / 100	92 ms	17328 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"

#define INF 1000000005
#define EPS 1e-6
#define pb push_back
#define pause system("pause")
#define exit exit(0)
#define endl '\n'

using namespace std;
using ull = unsigned long long;
using ll = long long;

typedef pair<int, int> pii;
const int N = 40005, LG = 16;

int n, m;

int st[LG][N], lg[N], ar[N];
string tr_ans;

int get(int l, int r) {
	int j = lg[r - l + 1];
	int f = st[j][l], s = st[j][r - (1 << j) + 1];
	return ar[f] > ar[s] ? f : s;
}

void dfs(int l, int r) {
	if (l > r) return;
	int j = get(l, r);
	tr_ans += '0' + (l <= j - 1);
	tr_ans += '0' + (j + 1 <= r);

	dfs(l, j - 1);
	dfs(j + 1, r);
}

void read_array(int subtask_id, const vector<int> &v) {
	vector<int> a(v.begin(), v.end());
	sort(a.begin(), a.end());	
	int n = v.size(), i = 0;
	for (auto x : v) {
		int j = lower_bound(a.begin(), a.end(), x) - a.begin();
		ar[i++] = j;
	}

	lg[0] = -1;
	for (int i = 0; i < n; ++i) {
		st[0][i] = i;
		lg[i + 1] = lg[(i + 1) >> 1] + 1;
	}

	for (int j = 1; j < LG; ++j) {
		for (int i = 0; i + (1 << j) - 1 < n; ++i) {
			st[j][i] = ar[st[j - 1][i]] > ar[st[j - 1][i + (1 << (j - 1))]] ? st[j - 1][i] : st[j - 1][i + (1 << (j - 1))];
		}
	}

	dfs(0, n - 1);

	save_to_floppy(tr_ans);
}

string tr_val;
int ptr, cv, l[N], r[N], pos[N], vt[N], dep[N], pa[LG][N];
vector<int> v;
int dfs() {
	int pp = ptr, cur = cv++;
	if (tr_val[pp] == '1') {
		ptr += 2;
		l[cur] = dfs();
	}

	if (tr_val[pp + 1] == '1') {
		ptr += 2;
		r[cur] = dfs();
	}

	return cur;
}

int dfs2(int u, int k = 0) {
	int ans = 1, v = 0;
	if (l[u]) {
		dep[l[u]] = dep[u] + 1;
		pa[0][l[u]] = u;
		v = dfs2(l[u], k);
		k += v, ans += v;
	}

	for (int j = 1; j < LG; ++j) {
		pa[j][u] = pa[j - 1][pa[j - 1][u]];
	}

	pos[u] = k, vt[k] = u;
	if (r[u]) {
		pa[0][r[u]] = u;
		dep[r[u]] = dep[u] + 1;
		ans += dfs2(r[u], k + 1);
	}

	return ans;
}

int lca(int u, int v) {
	if (dep[v] > dep[u]) swap(u, v);
	int h = dep[u] - dep[v];
	for (int j = 0; j < LG; ++j) {
		if ((h >> j) & 1) {
			u = pa[j][u];
		}
	}

	if (u == v) return u;
	for (int j = LG - 1; j >= 0; --j) {
		if (pa[j][u] != pa[j][v]) {
			u = pa[j][u], v = pa[j][v];
		}
	}

	return pa[0][u];
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
	vector<int> v;
	tr_val = bits;
	dfs();
	dfs2(0);

	int m = a.size();
	vector<int> ans(m);
	for (int i = 0; i < m; ++i) {
		ans[i] = pos[lca(vt[a[i]], vt[b[i]])];
	}

	return ans;
}

Compilation message (stderr)

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: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72