Submission #803049

#	Time	Username	Problem	Language	Result	Execution time	Memory
803049		LikeScience	Floppy (RMI20_floppy)	C++14	0 / 100	79 ms	13684 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#define F(i,s,e) for (int i = s; i<e; i++)
#define fi first
#define se second
#include "floppy.h"
using namespace std;

vector<pair<int, int> > st;
string str;
int id = -2;
int _n;

void stb(int l, int r, int x, const vector<int> &v) {
    if (l == r) {
        st[x].fi = v[l];
        st[x].se = l;
        return;
    } int m = (l+r)/2;
    stb(l,m,2*x+1,v);
    stb(m+1,r,2*x+2,v);
    if (st[2*x+1].fi > st[2*x+2].fi) {
        st[x] = st[2*x+1];
    } else {
        st[x] = st[2*x+2];
    }
}

pair<int, int> ste(int l, int r, int dl , int dr, int x) {
    if (l == dl && r == dr) {
        return st[x];
    } int m = (l+r)/2;
    if (dr <= m) {
        return ste(l,m,dl,dr,2*x+1);
    } else if (dl >= m+1) {
        return ste(m+1,r,dl,dr,2*x+2);
    } else {
        pair<int, int> a = ste(l,m,dl,m,2*x+1), b = ste(m+1,r,m+1,dr,2*x+2);
        if (a.fi>b.fi) {return a;} else return b;
    }
} 

void ctb(int l, int r) {
    id+=2;
    if (l == r) return;
    pair<int, int> p = ste(0,_n-1,l,r,0);
    if (p.se == l) {
        str[id+1]='1';
        ctb(p.se+1,r);
    } else if (p.se == r) {
        str[id]='1';
        ctb(l, p.se-1);
    } else {
        str[id]='1';
        str[id+1]='1';
        ctb(l, p.se-1);
        ctb(p.se+1,r);
        
    }
    
}

void read_array(int subtask_id, const std::vector<int> &v) {
    int n = (int)v.size(); _n = n;
    st.assign(4*n, make_pair(0,0));
    str.assign(2*n, '0');
    stb(0,n-1,0,v);
    ctb(0,n-1);
    save_to_floppy(str);
}

vector<int> l, r, p, sub, idx, fir, pth, dth, s2;

void dfs1(int v, const string &bits) {
    if (v != 0) dth[v] = dth[p[v]]+1;
    if (str[2*id] == '0' && str[2*id+1] == '0') { return;}
    if (str[2*v] == '1') {
        l[v] = ++id;
        p[id] = v;
        int k = id;
        dfs1(k,bits);
        sub[v] += sub[k];
    }
    if (str[2*v+1] == '1') {
        r[v] = ++id;
        p[id] = v;
        int k = id;
        dfs1(k,bits);
        sub[v] += sub[k];
    }

}
void aid(int le, int v) {
    idx[v] = le + (l[v] != -1 ? sub[l[v]] : 0);
    if (l[v] != -1) {
        aid(le,l[v]);
    } if (r[v] != -1) {
        aid(idx[v]+1, r[v]);
    } return;
}

void dfs2(int v) {
    pth.push_back(v);
    fir[idx[v]]=(int)pth.size()-1;
    if (l[v] != -1) {
        dfs2(l[v]);
        pth.push_back(v);
    } if (r[v] != -1) {
        dfs2(r[v]);
        pth.push_back(v);
    } return;
}

void s2b(int al, int ar, int x) {
    if (al == ar) {
        s2[x] = pth[al];
        return;
    } int m = (al+ar)/2;
    s2b(al,m,2*x+1);
    s2b(m+1,ar,2*x+2);
    if (dth[s2[2*x+1]] < dth[s2[2*x+2]]) {
        s2[x] = s2[2*x+1];  
    }else s2[x] = s2[2*x+2];
}
int s2e (int al, int ar, int dl, int dr, int x) {
    if (al == dl && ar == dr) {
        return s2[x];
    } int m = (al+ar)/2;
    if (dr <= m) {
        return s2e(al, m, dl, dr, 2*x+1);
    } else if (dl >= m+1) {
        return s2e( m+1, ar, dl, dr, 2*x+2);
    } else {
        int a = s2e(al, m, dl, m, 2*x+1), b = s2e( m+1, ar, m+1, dr, 2*x+2);
        if (dth[a] < dth[b]) {
            return a;
        } else return b;
    }
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    vector<int> ans;
    int m = (int)a.size();
    l.assign(N, -1); r.assign(N,-1); p.assign(N,-1); sub.assign(N,1); idx.assign(N,0); dth.assign(N,0); fir.assign(N,0);
    id = 0;
    dfs1(0, bits);
    aid(0, 0);
    dfs2(0);
    //F(i,0,N) cout << idx[i] << " " << idx[l[i]] << " " << idx[r[i]] << " " << idx[p[i]] << " " << sub[i] << " " << dth[i] << '\n';
    int ps = (int)pth.size();
    s2.assign(4*ps, 0);
    s2b(0, ps-1, 0);
    //F(i,0,N) cout << fir[idx[i]] << " "; 
    F(i,0,m) {
        ans.push_back(idx[s2e(0,ps-1,min(fir[a[i]], fir[b[i]]),max(fir[a[i]], fir[b[i]]),0)]);
        //cout << ans[i] << " ";
    }
    return ans;
}

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: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72