제출 #1225454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225454		Ghulam_Junaid	Floppy (RMI20_floppy)	C++20	28 / 100	1132 ms	6896 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], pos[MXN], tme, cur, lc[MXN], rc[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){
    if (bits[2 * v] == '1'){
        cur++;
        lc[v] = cur;
        dfs(cur);
    }
    pos[v] = tme++;
    if (bits[2 * v + 1] == '1'){
        cur++;
        rc[v] = cur;
        dfs(cur);
    }
}

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

    vector<int> answers;
    for (int i = 0; i < a.size(); i ++){
        int l = a[i], r = b[i];
        int v = 0;
        while (1){
            if (r < pos[v]) v = lc[v];
            else if (pos[v] < l) v = rc[v];
            else{
                answers.push_back(pos[v]);
                break;
            }
        }  
    }
    return answers;
}

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