제출 #1222363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222363		__moin__	Floppy (RMI20_floppy)	C++20	100 / 100	66 ms	8804 KiB

floppy

#include <bits/stdc++.h>
using namespace std;

#include "floppy.h"

vector<bool> construct(const vector<int>& v) {
    vector<bool> construction;
    stack<int> right_path; // save indizes
    right_path.push(0);
    for (int i = 1; i < v.size(); i++) {
        while (!right_path.empty() && v[right_path.top()] < v[i]) {
            right_path.pop();
            construction.push_back(0);
        }
        right_path.push(i);
        construction.push_back(1);
    }
    return construction;
}

tuple<int, vector<int>, vector<int>, vector<int>> reconstruct(int n, vector<bool>& construction) {
    int root = 0;
    vector<int> left(n, -1);
    vector<int> right(n, -1);
    vector<int> par(n, -1);
    stack<int> right_path;
    right_path.push(-1);
    right_path.push(0);
    int construction_idx = 0;
    for (int i = 1; i < n; i++) {
        int count = 0;
        while (construction[construction_idx] == 0) {
            construction_idx++;
            count++;
        }
        int to_replace = -1;
        for (int j = 0; j < count; j++) {
            to_replace = right_path.top();
            right_path.pop();
        }
        int p = right_path.top();
        if (p != -1) right[p] = i;
        else root = i;
        par[i] = p;
        if (to_replace != -1) par[to_replace] = i;
        left[i] = to_replace;
        
        right_path.push(i);
        construction_idx++;
    }
    return {root, left, right, par};
}

void read_array(int subtask_id, const std::vector<int> &v) {
    vector<bool> construction = construct(v);
    string bits;
    for (auto e : construction) bits.append(e ? "1" : "0");
    save_to_floppy(bits);
}

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<bool> construction(bits.size());
    for (int i = 0; i < bits.size(); i++) construction[i] = bits[i] == '1';
    auto [root, left, right, par] = reconstruct(N, construction);

    vector<vector<int>> jump(30, vector<int>(N));
    jump[0] = par;
    jump[0][root] = root;
    assert(all_of(jump[0].begin(), jump[0].end(), [&](int x){return x >= 0;}));
    for (int i = 1; i < 30; i++) {
        for (int u = 0; u < N; u++) {
            jump[i][u] = jump[i-1][jump[i-1][u]];
        }
    }

    vector<int> depth(N);
    function<void(int,int)> dfs = [&](int u, int dep) {
        if (u == -1) return;
        depth[u] = dep;
        dfs(left[u], dep+1);
        dfs(right[u], dep+1);
    };
    dfs(root, 0);

    function<int(int,int)> lift = [&](int u, int h) {
        for (int i = 29; i >= 0; i--) {
            if (h & (1 << i)) u = jump[i][u];
        }
        return u;
    };

    function<int(int,int)> lca = [&](int u, int v) {
        if (depth[u] > depth[v]) swap(u,v);
        v = lift(v, depth[v]-depth[u]);
        assert (depth[u] == depth[v]);
        if (u == v) return u;
        for (int i = 29; i >= 0; i--) {
            if (jump[i][u] != jump[i][v]) {
                u = jump[i][u];
                v = jump[i][v];
            }
        }
        return jump[0][u];
    };

    vector<int> ans(a.size());
    for (int i = 0; i < a.size(); i++) {
        assert (a[i] <= b[i]);
        ans[i] = lca(a[i], b[i]);
    }

    return ans;
}

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