| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 494468 |
2021-12-15T14:13:47 Z |
boykut |
Floppy (RMI20_floppy) |
C++14 |
|
46 ms |
3644 KB |
#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
void read_array(int subtask_id, const std::vector<int> &v) {
vector<int> x;
for (int i = 0; i < v.size(); i++) x.push_back(v[i]);
sort(begin(x), end(x));
x.erase(unique(begin(x), end(x)), end(x));
vector<int> new_v(v.size());
for (int i = 0; i < v.size(); i++) {
new_v[i] = lower_bound(x.begin(), x.end(), v[i]) - x.begin();
}
std::string bits;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < 15; j++) {
if (new_v[i] & (1 << j)) bits += "1";
else bits += "0";
}
}
save_to_floppy(bits);
}
struct SegmentTreeMax {
int n;
vector<pair<int, int>> t;
SegmentTreeMax(int n) : n(n), t((n << 2) + 1, {INT_MIN, INT_MIN}) {}
void update(int i, int x, int v, int vl, int vr) {
if (vl == vr) {
t[v] = {x, vl};
} else {
int vm = (vl + vr) >> 1;
if (i <= vm)
update(i, x, v << 1, vl, vm);
else
update(i, x, v << 1 | 1, vm + 1, vr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
}
pair<int, int> query(int l, int r, int v, int vl, int vr) {
if (l > vr || vl > r) return {INT_MIN, INT_MIN};
else if (l <= vl && vr <= r) return t[v];
else {
int vm = (vl + vr) >> 1;
auto L = query(l, r, v << 1, vl, vm);
auto R = query(l, r, v << 1 | 1, vm + 1, vr);
return max(L, R);
}
}
void update(int i, int x) {
update(i, x, 1, 0, n - 1);
}
pair<int, int> query(int l, int r) {
return query(l, r, 1, 0, n - 1);
}
};
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
std::vector<int> ans;
int M = a.size();
SegmentTreeMax st(N);
int j = 0;
for (int i = 0; i < N; i++) {
int cnt = 15, p = 1, sum = 0;
while (cnt--) {
if (bits[j] == '1') sum += p;
p <<= 1;
j++;
}
st.update(i, sum);
}
for (int i = 0; i < M; i++) {
ans.push_back(st.query(a[i], b[i]).second);
}
return ans;
}
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for (int i = 0; i < v.size(); i++) x.push_back(v[i]);
| ~~^~~~~~~~~~
floppy.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
floppy.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i < v.size(); 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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
776 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
764 KB |
Output is correct |
| 5 |
Correct |
3 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
38 ms |
3644 KB |
Partially correct |
| 2 |
Partially correct |
38 ms |
3604 KB |
Partially correct |
| 3 |
Partially correct |
37 ms |
3456 KB |
Partially correct |
| 4 |
Partially correct |
41 ms |
3508 KB |
Partially correct |
| 5 |
Partially correct |
38 ms |
3632 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
3004 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
