oj.uz

Submission #922883

# Submission time Handle Problem Language Result Execution time Memory
922883 2024-02-06T08:48:07 Z bachhoangxuan Floppy (RMI20_floppy) C++17
100 / 100
 102 ms 23876 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 828 KB Output is correct
2 Correct 1 ms 820 KB Output is correct
3 Correct 2 ms 832 KB Output is correct
4 Correct 1 ms 828 KB Output is correct
5 Correct 2 ms 828 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5568 KB Output is correct
2 Correct 22 ms 5472 KB Output is correct
3 Correct 26 ms 6320 KB Output is correct
4 Correct 27 ms 5904 KB Output is correct
5 Correct 20 ms 5552 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 19944 KB Output is correct
2 Correct 87 ms 20036 KB Output is correct
3 Correct 102 ms 23876 KB Output is correct
4 Correct 98 ms 21848 KB Output is correct
5 Correct 87 ms 19844 KB Output is correct