제출 #1218449

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

floppy

#include <bits/stdc++.h>

using namespace std;

//~ #define int long long

string str;
int zp;
vector<pair<int, int>> segtree;

int lg = 14;

void save_to_floppy(const string &bits);

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

void read_array(int subtask_id, const vector<int> &v) {
	vector<pair<int, int>> srt;
	int n = v.size();
	lg = log2(2*n-1);
	for (int i = 0; i < n; i++) {
		srt.push_back({v[i], i});
	}
	sort(srt.begin(), srt.end());
	vector<int> num(n);
	for (int i = 0; i < n; i++) num[srt[i].second] = i;
	string res;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < lg; j++) {
			if ((1<<j)&num[i]) res.push_back('1');
			else res.push_back('0');
		}
	}
	//~ cout << res << endl;
	str = res;
	save_to_floppy(res);
}

vector<int> number() { //turns bits into 
	vector<int> res;
	for (int i = 0; i < (int)str.size(); i += lg) {
		int curr = 0;
		for (int j = 0; j < lg; j++) {
			if (str[i+j] == '1') curr += (1<<j);
		}
		res.push_back(curr);
	}
	return res;
}

pair<int, int> query(int l, int r, int lb = 0, int rb = zp-1, int idx = 1) {
	if (l <= lb && r >= rb) return segtree[idx];
	if (l > rb || r < lb) return {-1, -1};
	int m = (lb+rb)/2;
	pair<int, int> left = query(l, r, lb, m, idx*2);
	pair<int, int> right = query(l, r, m+1, rb, idx*2+1);
	if (left.first > right.first) return left;
	else return right;
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
	vector<int> ans;
	str = bits;
	lg = log2(2*N-1);
	vector<int> info = number();
	//~ for (int i : info) cout << i << " ";
	int tmp = log2(2*N-1);
	zp = 1<<tmp;
	segtree = vector<pair<int, int>> (2*zp, {0, 0});
	//~ cout << "AA" << endl;
	for (int i = 0; i < N; i++) {
		segtree[i+zp] = {info[i], i};
	}
	//~ cout << "AA" << endl;
	for (int i = zp-1; i > 0; i--) {
		if (segtree[i*2].first > segtree[i*2+1].first) {
			segtree[i] = segtree[i*2];
		} else segtree[i] = segtree[i*2+1];
	}
	//~ cout << "AA" << endl;
	for (int q = 0; q < (int)a.size(); q++) {
		ans.push_back(query(a[q], b[q]).second);
	}
	//~ for (int i : ans) cout << i << " ";
	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});
	//~ 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: 0 / 72