oj.uz

답안 #850331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850331 2023-09-16T11:46:53 Z TahirAliyev Floppy (RMI20_floppy) C++17
0 / 100
 24 ms 4688 KB 
#include <bits/stdc++.h>

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

using namespace std;

const int MAX = 4e4 + 4, LOGMAX = 17;
int n;
int arr[MAX];
pii tree[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));
}

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 + 1;
    if(!L[node]){
        a = ad + 1;
    }
    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]){
        if(L[node]){
            dfs(R[node], ad + sub[L[node]] + 1 , a);
        }
        else{
            dfs(R[node], ad + 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);
    dfs(0, 0, 0);
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; 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] + 1, b[i] + 1) - 1);
    }
    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:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 2392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -