Submission #1263552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263552		altern23	Floppy (RMI20_floppy)	C++20	14.29 / 100	26 ms	3144 KiB

floppy

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

#define fi first
#define sec second

const int LOG = 15;

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

    int N = v.size();
    for(int i = 0; i < N; i++){
        isi.push_back({v[i], i});
    }
    sort(isi.begin(), isi.end());
    
    int cur = 0;
    for(auto &[val, idx] : isi){
        val = ++cur;
    }

    sort(isi.begin(), isi.end(), [&](pair<int, int> a, pair<int, int> b){
        return a.sec < b.sec;
    });

    string bits = "";
    for(auto &[val, idx] : isi){
        for(int j = 0; j < LOG; j++){
            bits.push_back(((val >> j) & 1) + '0');
        }
    }

    save_to_floppy(bits);
}

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 = 0; i < N; i++){
        int val = 0;
        for(int j = i * LOG; j < i * LOG + LOG; j++){
            val += (1LL << (j - i * LOG)) * (bits[j] == '1');
        }
        arr.push_back(val);
    }

    vector<int> lg(N + 5);
    for(int i = 2; i <= N; i++) lg[i] = lg[i / 2] + 1;

    vector<vector<pair<int, int>>> sp(N, vector<pair<int, int>>(20));
    for(int log = 0; log < 20; log++){
        for(int i = 0; i < N; i++){
            if(log == 0) sp[i][log] = {arr[i], i};
            else{
                if(i + (1LL << (log - 1)) < N) sp[i][log] = max(sp[i][log - 1], sp[i + (1LL << (log - 1))][log - 1]);
            }
        }
    }

    auto query = [&](int l, int r){
        return max(sp[l][lg[r - l + 1]], sp[r - (1LL << lg[r - l + 1]) + 1][lg[r - l + 1]]).sec;
    };

    for(int i = 0; i < Q; i++){
        answers.push_back(query(a[i], b[i]));
    }
    
    return answers;
}

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