Submission #922883

#	Time	Username	Problem	Language	Result	Execution time	Memory
922883		bachhoangxuan	Floppy (RMI20_floppy)	C++17	100 / 100	102 ms	23876 KiB

floppy

#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int maxn=40005;
const int maxl=20;
#define pii pair<int,int>
#define fi first
#define se second

void read_array(int subtask_id, const std::vector<int> &v) {
    string bits;
    int n=(int)v.size();
    vector<int> lt(n),rt(n),x;
    for(int i=0;i<n;i++){
        while(!x.empty() && v[x.back()]<v[i]) x.pop_back();
        lt[i]=(x.empty()?0:x.back()+1);
        x.push_back(i);
    }
    x.clear();
    for(int i=n-1;i>=0;i--){
        while(!x.empty() && v[x.back()]<v[i]) x.pop_back();
        rt[i]=(x.empty()?n-1:x.back()-1);
        x.push_back(i);
    }
    map<pii,int> mp;
    for(int i=0;i<n;i++) mp[{lt[i],rt[i]}]=i;
    int root=-1;
    vector<int> lc(n,-1),rc(n,-1);
    for(int i=0;i<n;i++){
        if(lt[i]<i) lc[i]=(mp[{lt[i],i-1}]);
        if(i<rt[i]) rc[i]=(mp[{i+1,rt[i]}]);
        if(lt[i]==0 && rt[i]==n-1) root=i;
    }
    function<void(int)> dfs = [&](int u){
        if(u==-1){
            bits+='0';
            return;
        }
        bits+='1';
        dfs(lc[u]);
        dfs(rc[u]);
    };
    dfs(root);
    save_to_floppy(bits);
}

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 m=(int)a.size();
    vector<int> res(m,-1),lc(n,-2),rc(n,-2);
    int pos=0;
    stack<int> s;
    vector<int> ind(n,-1),f(n,-1),dep(n,0);
    vector<vector<int>> par(n,vector<int>(maxl,-1));
    //cout << bits << '\n';
    for(char c:bits){
        while(!s.empty() && (lc[s.top()]!=-2 && rc[s.top()]!=-2)) s.pop();
        if(c=='1'){
            if(!s.empty()){
                int u=s.top();
                if(lc[u]==-2) lc[u]=pos;
                else rc[u]=pos;
            }
            s.push(pos++);
        }
        else{
            int u=s.top();
            if(lc[u]==-2) lc[u]=-1;
            else rc[u]=-1;
        }
    }
    int cnt=0;
    function<void(int)> dfs = [&](int u){
        if(lc[u]!=-1){
            dep[lc[u]]=dep[u]+1;
            par[lc[u]][0]=u;
            dfs(lc[u]);
        }
        f[cnt]=u;
        ind[u]=cnt++;
        if(rc[u]!=-1){
            dep[rc[u]]=dep[u]+1;
            par[rc[u]][0]=u;
            dfs(rc[u]);
        }
    };
    dfs(0);

    for(int i=1;i<maxl;i++){
        for(int u=0;u<n;u++) if(par[u][i-1]!=-1) par[u][i]=par[par[u][i-1]][i-1];
    }
    auto lca = [&](int u,int v){
        if(dep[u]>dep[v]) swap(u,v);
        for(int i=0;i<maxl;i++) if((dep[v]-dep[u])>>i&1) v=par[v][i];
        if(u==v) return u;
        for(int i=maxl-1;i>=0;i--){
            if(par[u][i]!=par[v][i]){
                u=par[u][i];
                v=par[v][i];
            }
        }
        return par[u][0];
    };
    for(int i=0;i<m;i++){
        int A=f[a[i]];
        int B=f[b[i]];
        res[i]=ind[lca(A,B)];
    }
    return res;
}

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