oj.uz

Submission #857322

# Submission time Handle Problem Language Result Execution time Memory
857322 2023-10-05T22:05:33 Z zsombor Floppy (RMI20_floppy) C++17
28 / 100
 80 ms 25632 KB 
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
using namespace std;

int n;
vector <int> v(8e4, -2e9);
vector <int> log2(4e4, 0);
vector <vector <int>> st(8e4, vector <int> (16, 0));
string b;
vector <int> p;

void build_st() {
    log2.assign(4e4, 0);
    for (int i = 2; i <= n; i++) log2[i] = log2[i / 2] + 1;
    st.resize(8e4);
    for (int i = 0; i < 8e4; i++) {
        st[i].assign(16, 0);
        st[i][0] = i;
    }
    for (int j = 1; j < 16; j++) {
        for (int i = 0; i < n; i++) {
            int x = st[i][j - 1], y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (v[x] > v[y] ? x : y);
        }
    }
}

int query_st(int l, int r) {
    int l2 = log2[r - l + 1], x = st[l][l2], y = st[r - (1 << l2) + 1][l2];
    return (v[x] > v[y] ? x : y);
}

void get_b(int l, int r) {
    if (l > r) return;
    int x = query_st(l, r);
    b.push_back('0');
    get_b(l, x - 1);
    b.push_back('1');
    get_b(x + 1, r);
}

void get_p() {
    p.assign(4e4, -1);
    vector <int> last(5e4, -1);
    int sum = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (b[i] == '0') {
            last[sum] = i;
            sum++;
        } else {
            sum--;
            p[last[sum]] = i;
        }
    }
}

void get_v(int l, int r, int val) {
    if (l > r) return;
    get_v(l + 1, p[l] - 1, val - 1);
    v.push_back(val);
    get_v(p[l] + 1, r, val - 1);
}

void read_array(int subt, const vector<int> &V) {
    n = V.size();
    v.assign(8e4, -2e9);
    for (int i = 0; i < n; i++) v[i] = V[i];
    build_st();
    get_b(0, n - 1);
    save_to_floppy(b);
}

vector <int> solve_queries(int subt, int N, const string &B, const vector<int> &L, const vector<int> &R) {
    n = N, b = B;
    get_p();
    v.clear();
    get_v(0, 2 * n - 1, 0);
    v.resize(8e4, -2e9);
    build_st();
    vector <int> ans;
    for (int i = 0; i < L.size(); i++) ans.push_back(query_st(L[i], R[i]));
    return ans;
}

Compilation message

floppy.cpp:9:14: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
    9 | vector <int> log2(4e4, 0);
      |              ^~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < L.size(); i++) ans.push_back(query_st(L[i], R[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 14 ms 18504 KB Output is correct
2 Correct 12 ms 18560 KB Output is correct
3 Correct 12 ms 18512 KB Output is correct
4 Correct 12 ms 18488 KB Output is correct
5 Correct 16 ms 18516 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20072 KB Output is correct
2 Correct 28 ms 20732 KB Output is correct
3 Correct 29 ms 20972 KB Output is correct
4 Correct 28 ms 21252 KB Output is correct
5 Correct 28 ms 20724 KB Output is correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 25632 KB Output isn't correct
2 Halted 0 ms 0 KB -