oj.uz

Submission #857326

# Submission time Handle Problem Language Result Execution time Memory
857326 2023-10-05T22:19:55 Z zsombor Floppy (RMI20_floppy) C++17
100 / 100
 81 ms 29148 KB 
#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

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 15 ms 18564 KB Output is correct
2 Correct 18 ms 18576 KB Output is correct
3 Correct 13 ms 18556 KB Output is correct
4 Correct 13 ms 18568 KB Output is correct
5 Correct 14 ms 18560 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20328 KB Output is correct
2 Correct 31 ms 20436 KB Output is correct
3 Correct 29 ms 20600 KB Output is correct
4 Correct 31 ms 20344 KB Output is correct
5 Correct 30 ms 20140 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 26136 KB Output is correct
2 Correct 81 ms 27876 KB Output is correct
3 Correct 80 ms 29148 KB Output is correct
4 Correct 78 ms 28928 KB Output is correct
5 Correct 76 ms 28048 KB Output is correct