| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 827139 |
2023-08-16T09:12:10 Z |
rainboy |
Floppy (RMI20_floppy) |
C++17 |
|
77 ms |
17152 KB |
#include "floppy.h"
#include <functional>
using namespace std;
typedef vector<int> vi;
void read_array(int subtask_id, const vi &aa) {
const int N = 40000;
int qu[N];
int n = aa.size();
string cc(n * 2, 0);
int cnt = 0, h = 0;
for (int i = 0; i < n; i++) {
while (cnt && aa[qu[cnt - 1]] <= aa[i])
cc[h++] = '1', cnt--;
cc[h++] = '0', qu[cnt++] = i;
}
while (cnt)
cc[h++] = '1', cnt--;
save_to_floppy(cc);
}
vi solve_queries(int subtask_id, int n, const string &cc, const vi &ii, const vi &jj) {
const int N = 40000;
int qu[N], ll[N], rr[N];
int *ej[N], eo[N];
function<void(int, int)> append = [&](int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
};
int dd[N], pp[N], qq[N];
function<int(int, int, int)> dfs1 = [&](int p, int i, int d) {
dd[i] = d, pp[i] = p;
int s = 1, k_ = 0, j_ = -1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
int k = dfs1(i, j, d + 1);
s += k;
if (k_ < k)
k_ = k, j_ = j;
}
}
qq[i] = j_;
return s;
};
function<void(int, int, int)> dfs2 = [&](int p, int i, int q) {
int j_ = qq[i]; qq[i] = q;
if (j_ != -1)
dfs2(i, j_, q);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != j_)
dfs2(i, j, j);
}
};
function<int(int, int)> lca = [&](int i, int j) {
while (qq[i] != qq[j])
if (dd[qq[i]] > dd[qq[j]])
i = pp[qq[i]];
else
j = pp[qq[j]];
return dd[i] < dd[j] ? i : j;
};
int cnt = 0;
for (int h = 0, i = 0; h < n * 2; h++)
if (cc[h] == '0')
ll[i] = cnt == 0 ? -1 : qu[cnt - 1], qu[cnt++] = i++;
else
rr[qu[--cnt]] = i;
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
int r = -1;
for (int i = 0; i < n; i++)
if (ll[i] == -1 && rr[i] == n)
r = i;
else if (ll[i] != -1 && rr[ll[i]] <= rr[i])
append(ll[i], i);
else
append(rr[i], i);
dfs1(-1, r, 0);
dfs2(-1, r, r);
int q = ii.size();
vi ans(q, 0);
for (int h = 0; h < q; h++)
ans[h] = lca(ii[h], jj[h]);
for (int i = 0; i < n; i++)
free(ej[i]);
return ans;
}
Compilation message
floppy.cpp: In lambda function:
floppy.cpp:30:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
30 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
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 |
2216 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2220 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
18 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
18 ms |
5756 KB |
Output is correct |
| 4 |
Correct |
19 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
18 ms |
4904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
13848 KB |
Output is correct |
| 2 |
Correct |
72 ms |
13964 KB |
Output is correct |
| 3 |
Correct |
70 ms |
17152 KB |
Output is correct |
| 4 |
Correct |
69 ms |
15432 KB |
Output is correct |
| 5 |
Correct |
69 ms |
13888 KB |
Output is correct |
