Submission #1056939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056939		Mighilon	Floppy (RMI20_floppy)	C++17	100 / 100	124 ms	21892 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
using namespace std;

#include "floppy.h"

void read_array(int subtask_id, const std::vector<int> &v) {
    int n = v.size();
    map<int, int> mp;
    for(auto i: v) mp[i]++;
    vector<int> a(n);
    int cnt = 0;
    for(auto& i: mp) i.second = cnt++;
    for(int i = 0; i < n; ++i) a[i] = mp[v[i]];
    cnt--;
    string bits = "";

    struct node{
        int p, l, r;
    };
    vector<node> tree(n + 1);
    tree[0] = {0, 0, 0};
    for(int i = 1; i <= n; ++i){
        tree[i].p = i - 1;
        while(tree[i].p > 0 && a[tree[i].p - 1] < a[i - 1]){
            bits.push_back('0');
            tree[i].p = tree[tree[i].p].p;
        }
        tree[i].l = tree[tree[i].p].r;
        tree[tree[i].p].r = i;
        tree[tree[i].l].p = i;
        bits.push_back('1');
    }
    save_to_floppy(bits);
}

void dfs(vector<vector<int>>& adj, vector<int>& dist, int u, int d){
    dist[u] = d;
    for(auto& v: adj[u]){
        if(u == v)
            continue;
        dfs(adj, dist, v, d + 1);
    }
};
std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    
    int n = N;
    struct node{
        int l, p, r;
    };
    vector<node> tree(n + 1);
    tree[0] = {0, 0, 0};
    for(int i = 1; i < n + 1; ++i)
        tree[i].p = i - 1;
    int j = 1;
    for(int i = 0; i < (int)bits.size(); ++i){
        if(bits[i] == '1'){
            tree[j].l = tree[tree[j].p].r;
            tree[tree[j].p].r = j;
            tree[tree[j].l].p = j;
            j++;
        }
        else{
            tree[j].p = tree[tree[j].p].p;
        }
    }
    int root = -1;
    vector<int> p(n);
    for(int i = 0; i < n; ++i){
        p[i] = tree[i + 1].p - 1;
        if(p[i] == -1)
            p[i] = i, root = i;
    }
    vector<vector<pair<int, int>>> jump(17, vector<pair<int, int>>(n));
    for(int i = 0; i < n; i++)
        jump[0][i] = {p[i], i};
    for(int k = 1; k < 17; ++k)
        for(int i = 0; i < n; ++i){
            if(jump[k - 1][i].first == -1)
                jump[k][i] = jump[k - 1][i];
            else jump[k][i] = jump[k - 1][jump[k - 1][i].first];
        }
    
    vector<int> dist(n, 0);
    vector<vector<int>> adj(n);
    for(int i = 0; i < n; ++i)
        adj[p[i]].push_back(i);
    dfs(adj, dist, root, 0);

    auto jump_k = [&](pair<int, int> a, int k){
        for(int i = 0; i < 17; ++i)
            if(k & (1 << i)){
                if(a.first == -1)
                    return a;
                a = jump[i][a.first];
            }
        return a;
    };

    auto lca = [&](pair<int, int> a, pair<int, int> b){
        if(a.first == -1)
            return a;
        if(b.first == -1)
            return b;
        
        if(dist[a.first] < dist[b.first])
            swap(a, b);
        int da = dist[a.first];
        int db = dist[b.first];
        if(da != db){
            int dif = da - db;
            a = jump_k(a, dif);
        }
        if(a == b)
            return a;
        for(int i = 16; i >= 0; --i){
            pair<int, int> ja = jump_k(a, 1 << i);
            pair<int, int> jb = jump_k(b, 1 << i);
            if(ja != jb)
                a = ja, b = jb;
        }
        return jump_k(a, 1);
    };

    
    
    vector<int> answers((int)a.size());
    for(int i = 0; i < (int)a.size(); ++i){
        answers[i] = lca({a[i], a[i]}, {b[i], b[i]}).second;
    }

    return answers;
}

Compilation message (stderr)

stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

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