| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 899955 |
2024-01-07T10:51:31 Z |
Cookie |
Floppy (RMI20_floppy) |
C++14 |
|
79 ms |
22604 KB |
#include<bits/stdc++.h>
#include<fstream>
#include "floppy.h"
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const int mxn = 40069;
string val = "";
int idnode = 1, idval = 0;
int adj[mxn + 1][2], tin[mxn + 1], tt = 0, tonode[mxn + 1], up[mxn + 1][16], dep[mxn + 1];
void dfs(int s){
if(val[idval] == '1'){
adj[s][0] = ++idnode; idval++; dep[adj[s][0]] = dep[s] + 1;
dfs(adj[s][0]); up[adj[s][0]][0] = s;
}else idval++;
tin[s] = tt; tonode[tt++] = s;
if(val[idval] == '1'){
adj[s][1] = ++idnode; idval++; dep[adj[s][1]] = dep[s] + 1;
dfs(adj[s][1]); up[adj[s][1]][0] = s;
}else idval++;
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);
int k = dep[u] - dep[v];
forr(i, 0, 16){
if(k & (1 << i))u = up[u][i];
}
if(u == v)return(u);
dorr(i, 15, 0){
if(up[u][i] != up[v][i]){
u = up[u][i]; v = up[v][i];
}
}
return(up[u][0]);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
val = bits;
dfs(1);
for(int i = 1; (1 << i) <= idnode; i++){
for(int j = 1; j <= idnode; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
for(int i = 1; i <= idnode; i++){
//cout << tin[i] << ' ';
//if(adj[i][0])cout << adj[i][0] << " ";
//if(adj[i][1])cout << adj[i][1] << " ";
//cout << "\n";
}
vt<int>answers;
for(int i = 0; i < sz(a); i++){
int u = tonode[a[i]], v = tonode[b[i]];
//cout << u << " " << v << "\n";
answers.pb(tin[lca(u, v)]);
}
//for(auto i: answers)cout << i << " ";
return answers;
}
pii mx[mxn + 1][16];
bool lson[mxn + 1], rson[mxn + 1];
pii getmx(int l, int r){
int lg = __lg(r - l + 1);
return(max(mx[l][lg], mx[r - (1 << lg) + 1][lg]));
}
string ans = "";
void build(int l, int r){
int id = getmx(l, r).se;
if(id != l){
ans += '1';
lson[id] = 1;
build(l, id - 1);
}else ans += '0';
if(id != r){
ans += '1';
rson[id] = 1;
build(id + 1, r);
}else{
ans += '0';
}
}
void read_array(int subtask_id, const std::vector<int> &v) {
for(int i = 0; i < sz(v); i++)mx[i][0] = mpp(v[i], i);
for(int i = 1; i < 16; i++){
for(int j = 0; j + (1 << i) - 1 < sz(v); j++){
mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
}
}
build(0, sz(v) - 1);
save_to_floppy(ans);
}
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 |
2868 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2880 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2872 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2872 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
8120 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
19 ms |
8276 KB |
Output is correct |
| 4 |
Correct |
19 ms |
8492 KB |
Output is correct |
| 5 |
Correct |
18 ms |
8128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
21328 KB |
Output is correct |
| 2 |
Correct |
72 ms |
21628 KB |
Output is correct |
| 3 |
Correct |
79 ms |
22604 KB |
Output is correct |
| 4 |
Correct |
77 ms |
22192 KB |
Output is correct |
| 5 |
Correct |
72 ms |
21412 KB |
Output is correct |
