Submission #924227

#	Time	Username	Problem	Language	Result	Execution time	Memory
924227		vjudge1	Floppy (RMI20_floppy)	C++17	100 / 100	136 ms	33120 KiB

floppy

#include<bits/stdc++.h>
#include "floppy.h"

using namespace std;

template<class T, class F>
struct sparse_table{
    int n;
    vector<vector<T>> data;
    F TT;
    T T_id;
    sparse_table(){ }
    // O(n log n)
    sparse_table(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id), data({a}){
        for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
            data.emplace_back(n - (p << 1) + 1);
            for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = TT(data[i - 1][j], data[i - 1][j + p]);
        }
    }
    // O(1)
    T query(int l, int r) const{
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return T_id;
        int d = __lg(r - l);
        return TT(data[d][l], data[d][r - (1 << d)]);
    }
};

pair<int, int> op(pair<int, int> a, pair<int, int> b) { return max(a, b); }

void read_array(int subtask_id, const std::vector<int> &v) {
    int n = (int)(v.size());
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) a[i] = {v[i], i};
    sparse_table st(a, op, pair{0, 0});

    vector<vector<int>> G(n);
    auto dfs = [&](auto self, int l, int r) -> int {
        if (l == r) return ~l;
        int pos = st.query(l, r).second;
        G[pos].emplace_back(self(self, l, pos));
        G[pos].emplace_back(self(self, pos + 1, r));
        return pos;
    };
    int root = dfs(dfs, 0, n);
    auto dfs2 = [&](auto self, int v) -> pair<int, string> {
        vector<pair<int, string>> vec;
        for (int u : G[v]) {
            if (u < 0) vec.emplace_back(u, "");
            else vec.push_back(self(self, u));
        }
        sort(vec.rbegin(), vec.rend());
        if (vec[0].second.empty() and vec[1].second.empty()) return {vec[0].first, "01"};
        if (vec[0].second.empty()) return {vec[0].first, "0" + vec[1].second + "1"};
        if (vec[1].second.empty()) return {vec[0].first, vec[0].second + "01"};
        return {vec[0].first, vec[0].second + "0" + vec[1].second + "1"};
    };
    save_to_floppy(dfs2(dfs2, root).second);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int n = (int)(bits.size()) / 2;
    vector<pair<int, int>> aa(n);
    for (int i = 0; i < n; ++i) aa[i].second = i;
    vector<int> posge(2 * n, -1);
    map<int, vector<int>> premp;
    int csum = 0;
    for (int i = 0; i < 2 * n; ++i) {
        if (bits[i] == '0') {
            premp[csum++].emplace_back(i);
        }
        else {
            csum--;
            int other = premp[csum].back();
            posge[other] = i, posge[i] = other;
            premp[csum].pop_back();
        }
    }
    // cerr << bits << endl;
    auto dfs = [&](auto self, int posl, int posr, int l, int r, int l1, int r1) -> void {
        // cout << "dfs: " << posl << " " << posr << " " << l << " " << r << " " << l1 << " " << r1 << endl;
        int len = posr - posl + 1, sum = 0, pos = posge[posr];
        if (len == 2) {
            aa[l].first = r1;
            return;
        }
        assert(pos != -1);
        if (pos == posl) {
            aa[l].first = r1;
            self(self, posl + 1, posr - 1, l + 1, r, l1, r1 - 1);
        }
        else if (pos == posr - 1) {
            aa[r].first = r1;
            self(self, posl, posr - 2, l, r - 1, l1, r1 - 1);
        }
        else {
            int inter = l + (pos - posl) / 2;
            aa[inter].first = r1;
            self(self, posl, pos - 1, l, inter - 1, l1, l1 + (pos - posl) / 2 - 1);
            self(self, pos + 1, posr - 1, inter + 1, r, l1 + (pos - posl) / 2, r1 - 1);
        }
    };
    dfs(dfs, 0, 2 * n - 1, 0, n - 1, 0, n - 1);
    sparse_table st(aa, op, pair{0, 0});
    vector<int> answers((int)(a.size()));
    for (int i = 0; i < (int)(a.size()); ++i) {
        answers[i] = st.query(a[i], b[i] + 1).second;
    }
    return answers;
}

Compilation message (stderr)

floppy.cpp: In instantiation of 'sparse_table<T, F>::sparse_table(const std::vector<_Tp>&, F, T) [with T = std::pair<int, int>; F = std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)]':
floppy.cpp:35:38:   required from here
floppy.cpp:11:7: warning: 'sparse_table<std::pair<int, int>, std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)>::T_id' will be initialized after [-Wreorder]
   11 |     T T_id;
      |       ^~~~
floppy.cpp:9:23: warning:   'std::vector<std::vector<std::pair<int, int> >, std::allocator<std::vector<std::pair<int, int> > > > sparse_table<std::pair<int, int>, std::pair<int, int> (*)(std::pair<int, int>, std::pair<int, int>)>::data' [-Wreorder]
    9 |     vector<vector<T>> data;
      |                       ^~~~
floppy.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     sparse_table(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id), data({a}){
      |     ^~~~~~~~~~~~
floppy.cpp: In instantiation of 'solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)::<lambda(auto:25, int, int, int, int, int, int)> [with auto:25 = solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)::<lambda(auto:25, int, int, int, int, int, int)>]':
floppy.cpp:103:46:   required from here
floppy.cpp:82:36: warning: unused variable 'sum' [-Wunused-variable]
   82 |         int len = posr - posl + 1, sum = 0, pos = posge[posr];
      |                                    ^~~
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