Submission #850371

#	Time	Username	Problem	Language	Result	Execution time	Memory
850371		TahirAliyev	Floppy (RMI20_floppy)	C++17	0 / 100	709 ms	15280 KiB

floppy

#include <bits/stdc++.h>

#include "floppy.h"
#define pii pair<int, int>
#define ll long long
#define oo 2e9

using namespace std;


const int MAX = 4e4 + 4, LOGMAX = 17;
int n;
int arr[MAX];
pii tree[4 * MAX];
string bits;

void build(int node, int l, int r){
    if(l == r){
        tree[node] = {arr[l], l};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

pii ask(int node, int l, int r, int ql, int qr){
    if(r < ql || qr < l){
        return {-oo, 0};
    }
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

int rec(int l, int r, int i){
    int m = ask(1, 1, n, l, r).second;
    int ni = i;
    if(l <= m - 1){
        bits[2 * i] = '1';
        ni = rec(l, m - 1, i + 1);
    }
    if(r >= m + 1){
        bits[2 * i + 1] = '1';
        ni = rec(m + 1, r, ni + 1);
    }
    return ni;
}


void read_array(int subtask_id, const std::vector<int> &v) {
    n = v.size();
    for(int i = 0; i < n; i++){    
        arr[i + 1] = v[i];
    }
    build(1, 1, n);
    bits.resize(2 * n, '0');
    rec(1, n, 0);
    save_to_floppy(bits);
}

int L[MAX], R[MAX];
int par[LOGMAX][MAX], timeIn[MAX], timeOut[MAX], sub[MAX];
int mp[MAX];

int rec(int node, string bits){
    int ni = node;
    if(bits[2 * node] == '1'){
        L[node] = node + 1;
        ni = rec(node + 1, bits);
    }
    if(bits[2 * node + 1] == '1'){
        R[node] = ni + 1;
        ni = rec(ni + 1, bits);
    }
    return ni;
}

void calcSub(int node){
    sub[node] = 1;
    if(L[node]){
        calcSub(L[node]);
        sub[node] += sub[L[node]];
    }
    if(R[node]){
        calcSub(R[node]);
        sub[node] += sub[R[node]];
    }
}

int t = 1;
void dfs(int node, int ad, int p){
    int a = sub[L[node]] + ad;
    timeIn[a] = t++;
    par[0][a] = p;
    if(node == 0){
        par[0][a] = a;
    }
    if(L[node]){
        dfs(L[node], ad, a);
    }
    if(R[node]){
        dfs(R[node], ad + sub[L[node]] + 1 , a);
    }
    timeOut[a] = t++;
}

bool isAnc(int u, int v){
    return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
}

int LCA(int u, int v){
    if(isAnc(u, v)) return u;
    if(isAnc(v, u)) return v;
    for(int j = LOGMAX - 1; j >= 0; j--){
        if(!isAnc(par[j][u], v)){
            u = par[j][u];
        }
    }
    return par[0][u];
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    rec(0, bits);
    calcSub(0);
    sub[0] = 0;
    dfs(0, 0, 0);
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 0; i < n; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    vector<int> ans;
    for(int i = 0; i < a.size(); i++){
        ans.push_back(LCA(a[i], b[i]));
    }
    return ans;
}

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:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     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