Submission #1136450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136450		Thanhs	Floppy (RMI20_floppy)	C++20	100 / 100	70 ms	11844 KiB

floppy

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

#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 4e4 + 5;

vector<int> g[NM];
string res;
int n, dep[NM], up[NM][21];
pair<int, int> st[NM][21];

int get(int l, int r)
{
    int L = __lg(r - l + 1);
    return max(st[l][L], st[r - (1 << L) + 1][L]).se;
}

void dnc(int l, int r)
{
    int m = get(l, r);
    if (l <= m - 1)
    {
        res += '1';
        dnc(l, m - 1);
    }
    else
        res += '0';
    if (m + 1 <= r)
    {
        res += '1';
        dnc(m + 1, r);
    }
    else
        res += '0';
}

void read_array(int _, const vector<int>& v)
{
    n = v.size();
    for (int i = 1; i <= n; i++)
        st[i][0] = {v[i - 1], i};
    for (int i = 1; (1 << i) <= n; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
    dnc(1, n);
    // cout << res << endl;
    save_to_floppy(res);
}

int p = 0;

pair<int, int> build(int c)
{
    int u = c + 1, cnt = 1;
    if (res[p++] == '1')
    {
        auto t = build(c);
        u += t.se;
        g[u].push_back(t.fi);
        up[t.fi][0] = u;
        c += t.se;
        cnt += t.se;
    }
    c++;
    if (res[p++] == '1')
    {
        auto t = build(c);
        g[u].push_back(t.fi);
        up[t.fi][0] = u;
        cnt += t.se;
    }
    return {u, cnt};
}

void dfs(int u)
{
    for (int v : g[u])
    {
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    int k = dep[u] - dep[v];
    while (k)
        u = up[u][__lg(k & -k)], k ^= k & -k;
    if (u == v)
        return u;
    for (int i = __lg(n); i >= 0; i--)
        if (up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

vector<int> solve_queries(int _, int N, const string& bits, const vector<int>& a, const vector<int>& b)
{
    n = N;
    res = bits;
    int root = build(0).fi;
    dfs(root);
    for (int i = 1; (1 << i) <= n; i++)
        for (int j = 1; j <= n; j++)
            up[j][i] = up[up[j][i - 1]][i - 1];
    vector<int> ans;
    for (int i = 0; i < (int)a.size(); i++)
        ans.push_back(lca(a[i] + 1, b[i] + 1) - 1);
    return ans;
}

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