Submission #858262

#	Time	Username	Problem	Language	Result	Execution time	Memory
858262		vivo2006	Floppy (RMI20_floppy)	C++14	0 / 100	72 ms	19692 KiB

floppy

#include<bits/stdc++.h>
#define MAXN 40004
#define INF -1000000001
#include "floppy.h"
using namespace std;
vector<int> arr;
pair<int, int> M[MAXN];
pair<int, int> cTree[MAXN];
string s;
int ind, indexx[MAXN], done, p[MAXN][16], level[MAXN];
struct segTree
{
    pair<int, int> tree[4 * MAXN];
    void build(int l, int r, int ind)
    {
        if(l == r)
        {
           tree[ind] = {arr[l], l};
           return;
        }
        int mid = (l + r) / 2;
        build(l, mid, ind * 2 + 1);
        build(mid + 1, r, ind * 2 + 2);
        tree[ind] = max(tree[ind * 2 + 1], tree[ind * 2 + 2]);
    }
    pair<int, int> query(int l, int r, int curL, int curR, int ind)
    {
        if(l > r) return {INF, INF};
        if(curL > r || curR < l) return {INF, INF};
        if(curL >= l && curR <= r) return tree[ind];
        int mid = (curL + curR) / 2;
        return max(query(l, r, curL, mid, ind * 2 + 1), query(l, r, mid + 1, curR, ind * 2 + 2));
    }
}st;
void buildBits(int l, int r, int curInd)
{
    pair<int, int> L = st.query(l, curInd - 1, 0, arr.size() - 1, 0);
    pair<int, int> R = st.query(curInd + 1, r, 0, arr.size() - 1, 0);
    cTree[curInd] = {INF, INF};
    if(L.first != INF)
    {
        cTree[curInd].first = L.second;
        buildBits(l, curInd - 1, L.second);
    }
    if(R.first != INF)
    {
        cTree[curInd].second = R.second;
        buildBits(curInd + 1, r, R.second);
    }
}
void dfs(int v)
{
    if(cTree[v].first != INF) s += "1";
    else s += "0";
    if(cTree[v].second != INF) s += "1";
    else s += "0";
    if(cTree[v].first != INF) dfs(cTree[v].first);
    if(cTree[v].second != INF) dfs(cTree[v].second);
}
void read_array(int subtask_id, const vector<int> &v)
{
    arr = v;
    st.build(0, v.size() - 1, 0);
    buildBits(0, v.size() - 1, st.tree[0].second);
    dfs(st.tree[0].second);
    save_to_floppy(s);
}
void DFS(int i)
{
    done = max(done, i);
    if(s[i] == '0')
    {
        indexx[i / 2] = ind ++;
    }
    else
    {
        DFS(i + 2);
        indexx[i / 2] = ind ++;
    }
    if(s[i + 1] == '1')
    {
        DFS(done + 2);
    }
}
void DFS2(int i, int lev)
{
    done = max(done, i);
    level[indexx[i / 2]] = lev;
    M[indexx[i / 2]] = {INF, INF};
    if(s[i] == '1')
    {
        M[indexx[i / 2]].first = indexx[(done + 2) / 2];
        p[indexx[(done + 2) / 2]][0] = indexx[i / 2];
        DFS2(i + 2, lev + 1);
    }
    if(s[i + 1] == '1')
    {
        M[indexx[i / 2]].second = indexx[(done + 2) / 2];
        p[indexx[(done + 2) / 2]][0] = indexx[i / 2];
        DFS2(done + 2, lev + 1);
    }
}
int solve(int a, int b)
{
    //cout<<a<<" "<<b<<endl;
    if(level[a] > level[b]) swap(a, b);
    int dif = -level[a] + level[b];
    for(int i = 0; i < 18; i ++)
    {
       if(dif & (1 << i))
       {
           b = p[b][i];
       }
    }
    //cout<<a<<" "<<b<<endl;
    if(a == b) return a;
    while(p[a][0] != p[b][0])
    {
        int tri = 0;
        while(p[a][tri] != p[b][tri]) tri ++;
        a = p[a][tri]; b = p[b][tri];
    }
    return p[a][0];
}
vector<int> solve_queries (int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b)
{
    s = bits;
    DFS(0);
    done = 0;
    /*for(int i = 0; i < bits.size() / 2; i ++)
    {
        cout<<indexx[i]<<endl;
    }*/
    p[0][0] = INF;
    DFS2(0, 0);
    vector<int> answers;
    /*for(int i = 0; i < bits.size() / 2; i ++)
    {
        cout<<M[i].first<<" "<<M[i].second<<endl;
    }*/
    for(int i = 0; i < a.size(); i ++)
    {
        answers.push_back(solve(a[i], b[i]));
        //cout<<endl;
    }
    return answers;

}
/*signed main()
{
    vector<int> v{40, 20, 30, 10};
    vector<int> a{0, 0, 0, 0, 1, 1, 1, 2, 2, 3};
    vector<int> b{0, 1, 2, 3, 1, 2, 3, 2, 3, 3};
    read_array(0, v);
    //cout<<"effefe"<<endl;
    vector<int> V = solve_queries(0, 4, s, a, b);
    for(int i = 0; i < V.size(); i ++) cout<<V[i]<<endl;
}*/

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < a.size(); i ++)
      |                    ~~^~~~~~~~~~
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