Submission #642894

#	Time	Username	Problem	Language	Result	Execution time	Memory
642894		lis05st	Floppy (RMI20_floppy)	C++17	0 / 100	632 ms	262144 KiB

floppy

#include <stdlib.h>
#include <string.h>

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

const int NMAX=2e5;
int ARR[NMAX+5],L[NMAX+5],R[NMAX+5],pr[NMAX+5];

string floppy;
vector<int>vec;
void dfs(int v){
    floppy+='0'+(L[v]==-1?0:1);
    floppy+='0'+(R[v]==-1?0:1);
    if(L[v]!=-1)dfs(L[v]);
    vec.push_back(ARR[v]);
    if(R[v]!=-1)dfs(R[v]);
}

int sL[NMAX+5],sR[NMAX+5],spr[20][NMAX+5];
int TIME=1,ID=0;
vector<int>arr;
int dfs2(string&s){
    bool haveLeft=s[ID]=='1';
    bool haveRight=s[ID+1]=='1';
    ID+=2;
    if(haveLeft){
        int x=dfs2(s);
        sL[TIME]=x;
        spr[0][x]=TIME;
    }
    int v=TIME;
    arr.push_back(v);
    spr[0][v]=v;
    TIME++;
    if(haveRight){
        int x=dfs2(s);
        sR[v]=x;
        spr[0][x]=v;
    }
    return v;
}
int tin[NMAX+5],tout[NMAX+5];
int T=0;
void dfs3(int v,int d){
    if(v==-1)return;
    tin[v]=++T;
    if(sL[v]==0)while(1){};
    if(sR[v]==0)while(1){};
    for(int lvl=1;lvl<=19;lvl++)spr[lvl][v]=spr[lvl-1][spr[lvl-1][v]];
    dfs3(L[v],d+1);
    dfs3(R[v],d+1);
    tout[v]=++T;
}

int restore(string s){
    memset(sL,-1,sizeof sL);
    memset(sR,-1,sizeof sR);
    int root=dfs2(s);
    return root;
}

bool aprofb(int a,int b){
    if(tin[a]<=tin[b]&&tout[b]<=tout[a])return 1;
    return 0;
}

int lca(int a,int b){
    if(aprofb(a,b))return a;
    if(aprofb(b,a))return b;
    //cout<<"LCA "<<a<<" "<<b<<"\n";
    for(int lvl=19;lvl>=0;lvl--){
        //cout<<lvl<<" "<<a<<" "<<b<<"\n";
        //cout<<spr[lvl][a]<<"\n";
        if(!aprofb(spr[lvl][a],b))a=spr[lvl][a];
    }
    return spr[0][a];
}

void read_array(int subtask_id, const std::vector<int> &v) {
    map<int,int>mp;
    vector<int>vec2;
    vector<int>v2=v;
    for(auto e:v)vec2.push_back(e);
    sort(vec2.begin(),vec2.end());
    for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
    for(auto&e:v2)e=mp[e];
    int n=v.size();
    for(int i=1;i<=n;i++)ARR[i]=v2[i-1];

    int root=1;
    L[root]=-1;
    R[root]=-1;
    pr[root]=-1;
    for(int i=2;i<=n;i++){
        L[i]=R[i]=-1;
        int last=i-1;
        while(last!=root&&ARR[last]<ARR[i])last=pr[last];
        if(ARR[last]<ARR[i]){
            root=i;
            L[i]=last;
            pr[last]=i;
        }
        else if(R[last]==-1){
            R[last]=i;
            pr[i]=last;
        }else{
            pr[i]=last;
            pr[R[last]]=i;
            L[i]=R[last];
            R[last]=i;
        }
    }
    dfs(root);
    save_to_floppy(floppy);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    string ss=bits;
    int root=restore(ss);
    assert(root!=-1);
    assert(arr.size()==N);
    dfs3(root,0);
    int n=bits.size()/2;
    std::vector<int> answers = vector<int>(a.size(),0);
    for(int i=0;i<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
    return answers;
}

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
      |                 ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from floppy.cpp:5:
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:125:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |     assert(arr.size()==N);
      |            ~~~~~~~~~~^~~
floppy.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
      |                 ~^~~~~~~~~
floppy.cpp:127:9: warning: unused variable 'n' [-Wunused-variable]
  127 |     int n=bits.size()/2;
      |         ^
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: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72