| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1056013 |
2024-08-13T07:10:02 Z |
Mighilon |
Floppy (RMI20_floppy) |
C++17 |
|
29 ms |
8564 KB |
#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
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
824 KB |
Output is correct |
| 3 |
Correct |
2 ms |
824 KB |
Output is correct |
| 4 |
Correct |
1 ms |
824 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
5012 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4816 KB |
Output is correct |
| 3 |
Correct |
25 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
20 ms |
5052 KB |
Output is correct |
| 5 |
Correct |
24 ms |
4780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
8564 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
