oj.uz

답안 #850402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850402 2023-09-16T14:01:31 Z TahirAliyev Floppy (RMI20_floppy) C++17
100 / 100
 81 ms 16788 KB 
#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 = 20;
int n;
int nxt = 0;
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 {0, 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));
}


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


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] + 1e9 + 100;
    }
    build(1, 1, n);
    bits.resize(2 * n, '0');
    rec(1, n);
    save_to_floppy(bits);
}

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


void rec(int node, const string& bits){
    if(bits[2 * node] == '1'){
        L[node] = nxt++;
        rec(L[node], bits);
    }
    if(bits[2 * node + 1] == '1'){
        R[node] = nxt++;
        rec(R[node], bits);
    }
}

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) {
    n = N;
    nxt = 1;
    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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6960 KB Output is correct
2 Correct 2 ms 6960 KB Output is correct
3 Correct 2 ms 6952 KB Output is correct
4 Correct 3 ms 6952 KB Output is correct
5 Correct 2 ms 6956 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 8756 KB Output is correct
2 Correct 19 ms 8748 KB Output is correct
3 Correct 18 ms 9272 KB Output is correct
4 Correct 20 ms 9112 KB Output is correct
5 Correct 22 ms 8752 KB Output is correct

Subtask #3
72.0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 15184 KB Output is correct
2 Correct 78 ms 15116 KB Output is correct
3 Correct 78 ms 16788 KB Output is correct
4 Correct 81 ms 15944 KB Output is correct
5 Correct 78 ms 15328 KB Output is correct