Submission #1204743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204743		1bin	Floppy (RMI20_floppy)	C++20	28 / 100	717 ms	327680 KiB

floppy

#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;
// }

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