oj.uz

Submission #857328

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

int n;
vector <int> v;
vector <int> Log2;
vector <vector <int>> st;
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(8e4, -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 = V;
    v.resize(8e4, -2e9);
    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: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     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 16 ms 18336 KB Output is correct
2 Correct 16 ms 18816 KB Output is correct
3 Correct 13 ms 18556 KB Output is correct
4 Correct 14 ms 18544 KB Output is correct
5 Correct 14 ms 18564 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 19936 KB Output is correct
2 Correct 30 ms 20328 KB Output is correct
3 Correct 28 ms 20280 KB Output is correct
4 Correct 30 ms 20448 KB Output is correct
5 Correct 30 ms 19932 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25968 KB Output is correct
2 Correct 77 ms 25916 KB Output is correct
3 Correct 77 ms 27296 KB Output is correct
4 Correct 78 ms 26968 KB Output is correct
5 Correct 80 ms 25952 KB Output is correct