oj.uz

Submission #857741

# Submission time Handle Problem Language Result Execution time Memory
857741 2023-10-06T19:19:29 Z lolismek Floppy (RMI20_floppy) C++14
100 / 100
 397 ms 19636 KB 
#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include <iostream>

const int NMAX = 40000;
const int INF = 1e9 + 1;

std::vector <int> V;

std::string lin = "";

void get_cart(int l, int r){
    int mini = -INF, pos = 0;
    for(int i = l; i <= r; i++){
        if(V[i] > mini){
            mini = V[i];
            pos = i;
        }
    }

    if(pos == l){
        lin += "0";
    }else{
        lin += "1";
    }

    if(pos == r){
        lin += "0";
    }else{
        lin += "1";
    }

    if(pos != l){
        get_cart(l, pos - 1);
    }
    if(pos != r){
        get_cart(pos + 1, r);
    }
}

void read_array(int subtask_id, const std::vector<int> &v){
    V = v;
    get_cart(0, (int)v.size() - 1);
    save_to_floppy(lin);
}

int ind = 0;
std::string S;

std::vector <int> adj[NMAX + 1];

int sz[NMAX + 1];
int lab[NMAX + 1];
int rlab[NMAX + 1];

const int LOG = 16;
int dp[NMAX + 1][LOG + 1];
int lvl[NMAX + 1];

int Node = 0;

int curr = 0;
int dfs(int parent){
    ++Node;

    bool l = (S[ind] == '1');
    bool r = (S[ind + 1] == '1');
    ind += 2;
    sz[Node] = 1;

    int node = Node;
    dp[node][0] = parent;
    lvl[node] = lvl[parent] + 1;

    int szl = 0;

    if(l){
        int lnode = dfs(node);
        adj[node].push_back(lnode);
        sz[node] += sz[lnode];
        szl = sz[lnode];
    }

    if(r){
        curr += sz[node];
        int rnode = dfs(node);
        curr -= sz[node];
        adj[node].push_back(rnode);
        sz[node] += sz[rnode];
    }

    lab[node] = curr + szl + 1;
    rlab[curr + szl + 1] = node;

    return node;
}

int LCA(int a, int b){
    if(lvl[a] < lvl[b]){
        std::swap(a, b);
    }

    int diff = lvl[a] - lvl[b];
    for(int i = LOG; i >= 0; i--){
        if(diff & (1 << i)){
            a = dp[a][i];
        }
    }

    if(a == b){
        return a;
    }

    for(int i = LOG; i >= 0; i--){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }

    return dp[a][0];
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    S = bits;

    dfs(0);

    std::vector <int> ans;

    for(int j = 1; (1 << j) <= N; j++){
        for(int i = 1; i <= N; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    for(int i = 0; i < (int)a.size(); i++){
        ans.push_back(lab[LCA(rlab[a[i] + 1], rlab[b[i] + 1])] - 1);
        //std::cout << ">> " << lab[LCA(rlab[a[i] + 1], rlab[b[i] + 1])] - 1 << std::endl;
    }

    return ans;
}

/*
1 6 4
4 5 1 6 2 3
3 5 4
0 5 2
0 1 0
0 2 2

3 4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/

Compilation message

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 4920 KB Output is correct
2 Correct 2 ms 4920 KB Output is correct
3 Correct 2 ms 4928 KB Output is correct
4 Correct 2 ms 4968 KB Output is correct
5 Correct 2 ms 4928 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8016 KB Output is correct
2 Correct 18 ms 7780 KB Output is correct
3 Correct 39 ms 8184 KB Output is correct
4 Correct 28 ms 8124 KB Output is correct
5 Correct 18 ms 7844 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17864 KB Output is correct
2 Correct 69 ms 17956 KB Output is correct
3 Correct 397 ms 19636 KB Output is correct
4 Correct 243 ms 19084 KB Output is correct
5 Correct 70 ms 17684 KB Output is correct