Submission #1264250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264250		altern23	Floppy (RMI20_floppy)	C++20	100 / 100	99 ms	11772 KiB

floppy

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

#define fi first
#define sec second
#define pii pair<int, int> 

const int LOG = 20;
const int MAXN = 4e4;

pii sp[MAXN + 5][LOG];
int lg[MAXN + 5], up[MAXN + 5][LOG], dist[MAXN + 5];
int L[MAXN + 5], R[MAXN + 5], id[MAXN + 5], sz[MAXN + 5];

pii query(int lf, int rg){
    return max(sp[lf][lg[rg - lf + 1]], sp[rg - (1LL << lg[rg - lf + 1]) + 1][lg[rg - lf + 1]]);
}

int dnc(int lf, int rg){
    if(lf > rg) return -1;
    pii now = query(lf, rg);
    L[now.sec] = dnc(lf, now.sec - 1);
    R[now.sec] = dnc(now.sec + 1, rg);
    return now.sec;
}

void dfs(int idx, string &bits){
    bits.push_back((L[idx] != -1) + '0');
    bits.push_back((R[idx] != -1) + '0');

    if(L[idx] != -1) dfs(L[idx], bits);
    if(R[idx] != -1) dfs(R[idx], bits);
}

void read_array(int subtask_id, const std::vector<int> &v) {
    vector<pair<int, int>> isi;

    int N = v.size();
    for(int i = 2; i <= N; i++) lg[i] = lg[i / 2] + 1;

    for(int log = 0; log < LOG; log++){
        for(int i = 0; i < N; i++){
            if(log == 0) sp[i][log] = {v[i], i};
            else{
                if(i + (1LL << (log - 1)) < N) sp[i][log] = max(sp[i][log - 1], sp[i + (1LL << (log - 1))][log - 1]);
            }
        }
    }

    string bits = "";

    dnc(0, N - 1);
    dfs(query(0, N - 1).sec, bits);

    save_to_floppy(bits);
}

int t = 0;
int now = 0;

void dfs2(int idx, const string &bits, int dep){
    bool lf = (bits[idx * 2] == '1');
    bool rg = (bits[idx * 2 + 1] == '1');
    sz[idx] = 1;
    if(!lf && !rg){
        id[idx] = t++;
        // cout << id[idx] << " LEAF\n";
        dist[id[idx]] = dep;
        return;
    }
    if(lf){
        dfs2(idx + 1, bits, dep + 1);
        // cout << t << " sini\n";
        // cout << "KIRI -> " << id[idx + 1] << "\n";
        sz[idx] += sz[idx + 1];
        up[id[idx + 1]][0] = t;
    }
    id[idx] = t++;
    if(rg){
        dfs2(idx + sz[idx], bits, dep + 1);
        up[id[idx + sz[idx]]][0] = id[idx];
        // cout << id[idx] << " sini\n";
        // cout << "KANAN -> " << id[idx + sz[idx]] << "\n";
        sz[idx] += sz[idx + sz[idx]];
    }
    dist[id[idx]] = dep;
    
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
    vector<int> answers;

    int Q = a.size();
    vector<int> arr;

    for(int i = 2; i <= N; i++) lg[i] = lg[i / 2] + 1;
    
    dfs2(0, bits, 0);

    for(int log = 1; log < LOG; log++){
        for(int i = 0; i < N; i++) up[i][log] = up[up[i][log - 1]][log - 1];
    }
    
    for(int i = 0; i < Q; i++){
        int A = a[i], B = b[i];
        // cout << A << " " << B << " SINI\n";
        // cout << dist[A] << " " << dist[B] << "\n";
        if(dist[A] < dist[B]){
            swap(A, B);
        }
        int res = dist[A] - dist[B];
        for(int j = 0; j < LOG; j++){
            if((res >> j) & 1) A = up[A][j];
        }
        if(A == B){
            // cout << A << "LCA\n";
            answers.push_back(A);
        }
        else{
            for(int j = LOG - 1; j >= 0; --j){
                if(up[A][j] != up[B][j]){
                    A = up[A][j];
                    B = up[B][j];
                }
            }
            answers.push_back(up[A][0]);
            // cout << up[A][0] << "LCA\n";
        }
        
    }
    
    return answers;
}

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