Submission #857326

#	Time	Username	Problem	Language	Result	Execution time	Memory
857326		zsombor	Floppy (RMI20_floppy)	C++17	100 / 100	81 ms	29148 KiB

floppy

#include <iostream>
#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.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 (stderr)

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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72