Submission #805575

#	Time	Username	Problem	Language	Result	Execution time	Memory
805575		M7kra	Floppy (RMI20_floppy)	C++17	7 / 100	251 ms	262144 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;
typedef pair<int, int> pii;

#include "floppy.h"

struct STree {
    int n;
    vector<int> elements;
    vector<int> index;

    STree (int size) {
        n = best2power(size);
        elements = vector<int>(n * 2, INF);
        index = vector<int>(n * 2);
    }

    void update(int k, int x) {
        k += n;
        elements[k] = x;
        index[k] = k - n;
        for (k /= 2; k >= 1; k /= 2) {
            int a = k * 2;
            int b = a + 1;
            if (elements[a] < elements[b]) {
                elements[k] = elements[a];
                index[k] = index[a];
            } else {
                elements[k] = elements[b];
                index[k] = index[b];
            }
        }
    }

    int get_min(int l, int r) {
        l += n;
        r += n;
        int current = INF;
        int current_index = -1;
        while (l <= r) {
            if (l & 1) {
                if (elements[l] < current) {
                    current = elements[l];
                    current_index = index[l];
                }
                l++;
            }
            if ((r & 1) == 0) {
                if (elements[r] < current) {
                    current = elements[r];
                    current_index = index[r];
                }
                r--;
            }

            l /= 2;
            r /= 2;
        }
        return current_index;
    }

    int best2power(int n) {
        int i = 1;
        while (i < n) i *= 2;
        return i;
    }
};

struct STreeMax {
    int n;
    vector<int> elements;
    vector<int> index;

    STreeMax (int size) {
        n = best2power(size);
        elements = vector<int>(n * 2);
        index = vector<int>(n * 2);
    }

    void update(int k, int x) {
        k += n;
        elements[k] = x;
        index[k] = k - n;
        for (k /= 2; k >= 1; k /= 2) {
            int a = k * 2;
            int b = a + 1;
            if (elements[a] > elements[b]) {
                elements[k] = elements[a];
                index[k] = index[a];
            } else {
                elements[k] = elements[b];
                index[k] = index[b];
            }
        }
    }

    int get_max(int l, int r) {
        l += n;
        r += n;
        int current = 0;
        int current_index = -1;
        while (l <= r) {
            if (l & 1) {
                if (elements[l] > current) {
                    current = elements[l];
                    current_index = index[l];
                }
                l++;
            }
            if ((r & 1) == 0) {
                if (elements[r] > current) {
                    current = elements[r];
                    current_index = index[r];
                }
                r--;
            }

            l /= 2;
            r /= 2;
        }
        return current_index;
    }

    int best2power(int n) {
        int i = 1;
        while (i < n) i *= 2;
        return i;
    }
};


struct CTreeFromSTree {
    int n;
    vector<pii> nodes;
    STreeMax stree;
    int root;

    CTreeFromSTree(int size, STreeMax tree): stree(tree) {
        n = size;
        nodes = vector<pii>(n, {-1, -1});
        stree = tree;
        root = build_node(0, n - 1);
    }

    int build_node(int l, int r) {
        if (l == r) return l;
        if (r < l || l > r) return -1;

        int n = stree.get_max(l, r);
        nodes[n] = {
            build_node(l, n - 1),
            build_node(n + 1, r)
        };

        return n;
    }

    string to_string() {
        return subtree_string(root);
    }

    string subtree_string(int n) {
        string s = "";
        if (nodes[n].first != -1) s += "1";
        else s += "0";
        if (nodes[n].second != -1) s += "1";
        else s += "0";

        if (nodes[n].first != -1) s += subtree_string(nodes[n].first);
        if (nodes[n].second != -1) s += subtree_string(nodes[n].second);
        return s;
    }
};

struct CTreeFromString {
    vector<pii> nodes;
    string str;
    int str_index = 0;
    vector<int> depths;

    CTreeFromString (string s) {
        nodes = vector<pii>(s.size() / 2);
        depths = vector<int>(s.size() / 2);
        str = s;
        rcs(0, 0);
    }

    int rcs(int previous, int depth) {
        int index;
        int result = -1;
        string s = read_s();
        if (s[0] == '0') index = previous;
        else index = rcs(previous, depth + 1) + 1;
        if (s[1] == '1') result = rcs(index + 1, depth + 1);
        depths[index] = depth;
        return result != -1? result : index;
    }

    string read_s() {
        string r = str.substr(str_index, 2);
        str_index += 2;
        return r;
    }
};

void read_array(int subtask_id, const std::vector<int> &v) {
    STreeMax stree(v.size());
    for (int i = 0; i < (int)v.size(); i++) stree.update(i, v[i]);
    CTreeFromSTree ctree((int)v.size(), stree);
    save_to_floppy(ctree.to_string());
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    CTreeFromString ctree(bits);
    STree stree(N);
    for (int i = 0; i < N; i++) stree.update(i, ctree.depths[i]);

    vector<int> answers(a.size());
    for (int i = 0; i < (int)a.size(); i++) {
        answers[i] = stree.get_min(a[i], b[i]);
    }

    return answers;
}

Compilation message (stderr)

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