제출 #1168796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168796		12345678	Floppy (RMI20_floppy)	C++20	100 / 100	65 ms	5336 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

const int nx=4e4+5, kx=16;

int l[nx], r[nx], pa[nx][kx], lvl[nx];

void dfs(int u, int p)
{
    pa[u][0]=p;
    lvl[u]=lvl[p]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    if (l[u]!=-1) dfs(l[u], u);
    if (r[u]!=-1) dfs(r[u], u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[u]<=lvl[pa[v][i]]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void read_array(int subtask_id, const std::vector<int> &v) {
    string str;
    stack<int> s;
    for (int i=0; i<v.size(); i++)
    {
        while (!s.empty()&&v[s.top()]<v[i]) s.pop(), str.push_back('1');
        s.push(i);
        str.push_back('0');
    }
    save_to_floppy(str);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    stack<int> s;
    int idx=0, rt=-1, cur=0;
    for (int i=0; i<N; i++) l[i]=r[i]=-1;
    //cout<<"bits "<<bits<<'\n';
    while (cur<bits.size())
    {
        //cout<<"here "<<cur<<' '<<bits[cur]<<' '<<bits.size()<<'\n';
        while (bits[cur]=='1') l[idx]=s.top(), cur++, s.pop();
        //cout<<"after\n";
        if (!s.empty()) r[s.top()]=idx;
        else rt=idx;
        cur++;
        s.push(idx++);
    }
    //for (int i=0; i<N;i ++) cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    dfs(rt, rt);
    vector<int> res;
    for (int i=0; i<a.size(); i++) res.push_back(lca(a[i], b[i])); //cout<<"val "<<a[i]<<' '<<b[i]<<' '<<lca(a[i], b[i])<<'\n';
    return res;
}
/*
g++ grader.cpp floppy.cpp -o a
*/

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