제출 #1219322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219322		damamila	Floppy (RMI20_floppy)	C++20	100 / 100	424 ms	5672 KiB

floppy

#include <bits/stdc++.h>

using namespace std;

//~ #define int long long

string str;
vector<int> num;
vector<int> rev;
int idx = 0;
int cnt = 0;
int over = 0;
vector<vector<int>> jump;
vector<int> dep;
int logn = 16;
int n;

vector<int> arr;

void save_to_floppy(const string &bits);

//~ void save_to_floppy(const string &bits) {
	//~ return;
//~ }

void construct(int l, int r) {
	if (l >= r) return;
	pair<int, int> ans = {-2e9, -1};
	for (int i = l; i < r; i++) {
		if (arr[i] > ans.first) {
			ans = {arr[i], i};
		}
	}
	if (l != ans.second) str.push_back('1');
	else str.push_back('0');
	if (r-1 != ans.second) str.push_back('1');
	else str.push_back('0');
	construct(l, ans.second);
	construct(ans.second+1, r);
}

void read_array(int subtask_id, const vector<int> &v) {
	arr = v;
	construct(0, v.size());
	//~ cout << str << endl;
	save_to_floppy(str);
}

void dfs(int p, int d) {
	int tmp = idx;
	idx += 2;
	int cnt2 = cnt;
	jump[0][cnt2] = p;
	dep[cnt2] = d;
	cnt++;
	if (str[tmp] == '1') {
		dfs(cnt2, d+1);
	}
	num[cnt2] = over;
	rev[over] = cnt2;
	over++;
	if (str[tmp+1] == '1') {
		dfs(cnt2, d+1);
	}
}

void pp() {
	for (int i = 1; i < logn; i++) {
		for (int j = 0; j < n; j++) {
			jump[i][j] = jump[i-1][jump[i-1][j]];
		}
	}
}

int lift(int a, int d) {
	for (int i = 0; i < logn; i++) {
		if (d & (1<<i)) {
			a = jump[i][a];
		}
	}
	return a;
}

int lca(int a, int b) {
	if (dep[b] > dep[a]) swap(a, b);
	a = lift(a, dep[a]-dep[b]);
	for (int i = logn-1; i >= 0; i--) {
		if (jump[i][a] != jump[i][b]) {
			a = jump[i][a];
			b = jump[i][b];
		}
	}
	if (a != b) {
		a = jump[0][a];
	}
	return a;
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
	str = bits;
	n = N;
	num = vector<int> (N, 0);
	rev = vector<int> (N, 0);
	dep = vector<int> (N, 0);
	jump = vector<vector<int>> (logn, vector<int> (N, 0));
	dfs(-1, 0);
	//~ for (int i : num) cout << i << " ";
	//~ cout << endl;
	//~ for (int i : jump[0]) cout << i << " ";
	//~ cout << endl;
	pp();
	vector<int> ans;
	for (int i = 0; i < (int)a.size(); i++) {
		int a1 = rev[a[i]];
		int b1 = rev[b[i]];
		int tmp = lca(a1, b1);
		//~ cout << tmp << " " << num[tmp] << endl;
		ans.push_back(num[tmp]);
	}
	return ans;
}

//~ signed main() {
	//~ read_array(3, {1, 3, 2, 4, 6, 5, 9});
	//~ vector<int> a = {0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6};
	//~ vector<int> b = {0, 1, 4, 6, 1, 2, 6, 2, 3, 3, 5, 5, 6};
	//~ read_array(3, {40, 20, 30, 10});
	//~ read_array(3, {40, 20, 30, 10});
	//~ vector<int> a = {0, 0, 0, 0, 1, 1, 1, 2, 2, 3};
	//~ vector<int> b = {0, 1, 2, 3, 1, 2, 3, 2, 3, 3};
	//~ solve_queries(3, 4, str, a, b);
//~ }

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