oj.uz

Submission #494521

# Submission time Handle Problem Language Result Execution time Memory
494521 2021-12-15T16:50:15 Z gesix56151 Floppy (RMI20_floppy) C++14
0 / 100
 97 ms 17368 KB 
#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);
	
	for (int u = 0; u < n; ++u) {	
		for (int j = 1; j < LG; ++j) {
			pa[j][u] = pa[j - 1][pa[j - 1][u]];
		}
	}

	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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 4632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 17368 KB Output isn't correct
2 Halted 0 ms 0 KB -