Submission #1056013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056013		Mighilon	Floppy (RMI20_floppy)	C++17	28 / 100	29 ms	8564 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
using namespace std;

#include "floppy.h"

void read_array(int subtask_id, const std::vector<int> &v) {
    map<int, int> mp;
    for(auto i: v) mp[i]++;
    vector<int> a(v.size());
    int cnt = 0;
    for(auto& i: mp) i.second = cnt++;
    for(int i = 0; i < (int)v.size(); ++i) a[i] = mp[v[i]];
    cnt--;
    auto code = [](int x) -> string{
        string a(14, '0');
        for(int i = 0; i < 14; ++i)
            if(x & (1 << i)) a[i] = '1';
        return a;
    };
    string bits = "";
    for(int i = 0; i < (int)a.size(); ++i){
        string x = code(a[i]);
        for(auto j: x)
            bits.push_back(j);
    }
    save_to_floppy(bits);
}

template<typename T>
struct SegTree{
    int size;
    const T DEFAULT = std::numeric_limits<T>().max();
    vector<T> t;
    vector<T> op;
    SegTree(int _size){
        if(__builtin_popcount(_size) != 1)
            _size = 1 << (32 - __builtin_clz(_size));
        size = _size;
        t.resize(size * 2, DEFAULT);
        op.resize(size * 2);
    }
    T merge(T a, T b){
        T c = max(a, b);
        return c;
    }
    void build(int x, int l, int r){
        if(l == r) return;
        int m = (l + r) / 2;
        build(2 * x, l, m);
        build(2 * x + 1, m + 1, r);
        t[x] = merge(t[2 * x], t[2 * x + 1]);
    }
    void add(int x, int l, int r, int ql, int qr, T val){
        if(r < ql || l > qr)
            return;
        if(l >= ql && r <= qr){
            t[x] += val;
            return;
        }
        int m = (l + r) / 2;
        add(2 * x, l, m, ql, qr, val);
        add(2 * x + 1, m + 1, r, ql, qr, val);
        t[x] = merge(t[2 * x], t[2 * x + 1]);
    }
    void add(int l, int r, T val){
        add(1, 0, size - 1, l, r, val);
    }
    void set(int i, T val){
        add(i, i, val - t[size + i]);
    }
    T query(int x, int l, int r, int ql, int qr){
        if(r < ql || l > qr)
            return DEFAULT;
        if(l >= ql && r <= qr)
            return t[x];
        int m = (l + r) / 2;
        return merge(query(2 * x, l, m, ql, qr), query(2 * x + 1, m + 1, r, ql, qr));
    }
    T query(int l, int r){
        return query(1, 0, size - 1, l, r);
    }
};

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    auto decode= [](string x) -> int{
        int a = 0;
        for(int i = 0; i < 14; ++i)
            if(x[i] == '1')
                a += 1 << i;
        return a;
    };
    vector<int> nums(N);
    for(int i = 0; i < N; ++i){
        string x = "";
        for(int j = 0; j < 14; ++j)
            x.push_back(bits[i * 14 + j]);
        nums[i] = decode(x);
    }
    SegTree<pair<int, int>> tree(N);
    for(int i = 0; i < N; ++i)
        tree.t[tree.size + i] = {nums[i], i};
    tree.build(1, 0, tree.size - 1);

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

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