| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1204745 | 1bin | Floppy (RMI20_floppy) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
//
// void save_to_floppy(string bits) {
// cout << bits << endl;
// return;
// }
void dfs(int x, vector<int> & L, vector<int>& R, string& bits) {
if (x == -1) return;
bits += (L[x] != -1) + '0';
bits += (R[x] != -1) + '0';
dfs(L[x], L, R, bits);
dfs(R[x], L, R, bits);
}
void read_array(int subtask_id, const vector<int> &v) {
int n = v.size(), x;
vector<vector<int>> adj(n, vector<int>());
vector<int> L(n, -1), R(n, -1);
stack<int> st;
string bits = "";
for (int i = 0; i < n; i++) {
while (st.size() && v[st.top()] < v[i]) {
int j = st.top(); st.pop();
if (st.empty() || v[st.top()] > v[i]) L[i] = j;
else R[st.top()] = j;
}
st.emplace(i);
}
while (st.size()) {
x = st.top(); st.pop();
if (st.size()) R[st.top()] = x;
}
dfs(x, L, R, bits);
save_to_floppy(bits);
}
const int B = 1 << 16;
int t, cur;
pair<int, int> seg[B * 2];
void find(string& bits, int v) {
int tmp = t++;
if (bits[tmp * 2] == '1') find(bits, v - 1);
seg[B + cur] = {v, cur};
cur++;
if (bits[tmp * 2 + 1] == '1') find(bits, v - 1);
}
int Max(int l, int r) {
l += B; r += B;
pair<int, int> ret = {0, 0};
while (l <= r) {
if (l & 1) ret = max(ret, seg[l++]);
if (!(r & 1)) ret = max(ret, seg[r--]);
l >>= 1;r >>= 1;
}
return ret.second;
}
vector<int> solve_queries(int subtask_id, int N,
const string &bits,
const vector<int> &a, const std::vector<int> &b) {
find(bits, N);
vector<int> ans;
for (int i = B - 1; i; i--) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
for (int i = 0; i < a.size(); i++) ans.emplace_back(Max(a[i], b[i]));
return ans;
}
// int main(void) {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
// // vector<int> v = {40, 20, 30, 10};
// // read_array(0, v);
//
// string bits = "01110000";
// 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};
//
// for (int& x : solve_queries(0, 4, bits, a, b)) cout << x << ' ';
// return 0;
// }