제출 #1225476

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

floppy

#include <bits/stdc++.h>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
// #include "grader.cpp"
using namespace std;

const int MXN = 1e5 + 10, LG = 18;
int n, sp[MXN][LG], par[MXN][LG], h[MXN], pos[MXN], tme, cur, lc[MXN], rc[MXN], rev[MXN];
vector<int> arr, order;
string bits;

int get(int l, int r){
    int lg = 31 - __builtin_clz(r - l + 1);
    int i = sp[l][lg], j = sp[r - (1 << lg) + 1][lg];
    if (arr[i] > arr[j]) return i;
    return j;
}

void dnc(int l, int r){
    if (l > r) return ;
    int mx = get(l, r);
    if (l == mx) bits += '0';
    else bits += '1';
    if (mx == r) bits += '0';
    else bits += '1';

    dnc(l, mx - 1);
    dnc(mx + 1, r);   
}

void read_array(int subtask_id, const vector<int> &v) {
    arr = v;
    n = arr.size();
    for (int i = 0; i < n; i ++)
        sp[i][0] = i;
    for (int j = 1; j < LG; j ++){
        for (int i = 0; i < n; i ++){
            int nxt = i + (1 << (j - 1));
            sp[i][j] = sp[i][j - 1];
            if (nxt < n and arr[sp[i][j]] < arr[sp[nxt][j - 1]])
                sp[i][j] = sp[nxt][j - 1];
        }
    }
    dnc(0, n - 1);
    save_to_floppy(bits);
}

void dfs(int v){
    for (int j = 1; j < LG; j ++)
        if (par[v][j - 1] != -1)
            par[v][j] = par[par[v][j - 1]][j - 1];

    if (bits[2 * v] == '1'){
        cur++;
        lc[v] = cur;
        par[cur][0] = v;
        h[cur] = h[v] + 1;
        dfs(cur);
    }
    rev[tme] = v;
    pos[v] = tme++;
    if (bits[2 * v + 1] == '1'){
        cur++;
        rc[v] = cur;
        par[cur][0] = v;
        h[cur] = h[v] + 1;
        dfs(cur);
    }
}

int lca(int u, int v){
    if (h[u] > h[v]) swap(u, v);
    int d = h[v] - h[u];
    for (int i = 0; i < LG; i ++)
        if ((1 << i) & d)
            v = par[v][i];

    if (u == v) return v;

    for (int i = LG - 1; i >= 0; i --)
        if (par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];
    return par[v][0];
}

vector<int> solve_queries(int subtask_id, int nn,
        const string &ss,
        const vector<int> &a, const vector<int> &b) {
    bits = ss, n = nn;
    memset(par, -1, sizeof par);
    dfs(0);

    vector<int> answers;
    for (int i = 0; i < a.size(); i ++){
        int l = a[i], r = b[i];
        int u = rev[l], v = rev[r];
        int L = lca(u, v);
        answers.push_back(pos[L]);
    }
    return answers;
}

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