oj.uz

Submission #848895

# Submission time Handle Problem Language Result Execution time Memory
848895 2023-09-13T16:39:05 Z TheSahib Floppy (RMI20_floppy) C++14
100 / 100
 84 ms 22680 KB 
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

const int MAX = 40005;
const int LOGMAX = 16;

pair<int, int> tree[MAX * 4];
int arr[MAX];

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

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

int n;
string s;
int nxt = 0;
void dfs1(int l, int r){
    pair<int, int> mx = ask(1, 0, n - 1, l, r);
    int id = nxt++;
    if(mx.second - 1  < l){
        s[id * 2] = '0';
    }
    else{
        s[id * 2] = '1';
        dfs1(l, mx.second - 1);
    }
    if(mx.second + 1 > r){
        s[id * 2 + 1] = '0';
    }
    else{
        s[id * 2 + 1] = '1';
        dfs1(mx.second + 1, r);
    }
}

void read_array(int subtask_id, const vector<int> &v) {
    n = v.size();
    for (int i = 0; i < n; i++)
    {
        arr[i] = v[i] + 1000000001;
    }
    build(1, 0, n - 1);
    s.resize(n * 2);
    dfs1(0, n - 1);
    save_to_floppy(s);
}

int par[LOGMAX][MAX];
vector<int> g[MAX];
int nxtItr = 0;
int dfs2(int itr){
    int node1 = -1, node2 = -1;
    if(s[itr] == '1'){
        nxtItr += 2;
        node1 = dfs2(nxtItr);
    }
    int node = nxt++;
    if(s[itr + 1] == '1'){
        nxtItr += 2;
        node2 = dfs2(nxtItr);
    }

    if(node1 != -1){
        par[0][node1] = node;
        g[node].push_back(node1);
    }
    if(node2 != -1){
        par[0][node2] = node;
        g[node].push_back(node2);
    }
    return node;
}
int t = 0;
int timeIn[MAX], timeOut[MAX];
void dfs3(int node){
    timeIn[node] = ++t;
    for(int to:g[node]){
        dfs3(to);
    }
    timeOut[node] = ++t;
}

bool isAncestor(int a, int b){
    return timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b];
}

int lca(int a, int b){
    if(isAncestor(a, b)) return a;
    if(isAncestor(b, a)) return b;

    for (int i = LOGMAX - 1; i >= 0; i--)
    {
        if(!isAncestor(par[i][a], b)){
            a = par[i][a];
        }
    }
    return par[0][a];
}

std::vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
    n = N;
    nxt = 0;
    s = bits;
    int r = dfs2(0);
    par[0][r] = r;
    for (int j = 1; j < LOGMAX; j++)
    {
        for (int i = 0; i < n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    dfs3(r);
    vector<int> ans(a.size());
    for (int i = 0; i < a.size(); i++)
    {
        ans[i] = lca(a[i], b[i]);
    }
    
    return ans;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9024 KB Output is correct
2 Correct 2 ms 9016 KB Output is correct
3 Correct 3 ms 9016 KB Output is correct
4 Correct 2 ms 9016 KB Output is correct
5 Correct 3 ms 9024 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11708 KB Output is correct
2 Correct 20 ms 11720 KB Output is correct
3 Correct 20 ms 12056 KB Output is correct
4 Correct 20 ms 11960 KB Output is correct
5 Correct 20 ms 11704 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21104 KB Output is correct
2 Correct 84 ms 21312 KB Output is correct
3 Correct 75 ms 22680 KB Output is correct
4 Correct 79 ms 22016 KB Output is correct
5 Correct 78 ms 21248 KB Output is correct