| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805575 |
2023-08-03T17:59:01 Z |
M7kra |
Floppy (RMI20_floppy) |
C++17 |
|
251 ms |
262144 KB |
#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
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 |
664 KB |
Output is correct |
| 2 |
Correct |
2 ms |
656 KB |
Output is correct |
| 3 |
Correct |
2 ms |
784 KB |
Output is correct |
| 4 |
Correct |
2 ms |
784 KB |
Output is correct |
| 5 |
Correct |
2 ms |
656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
251 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
251 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
