| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 924281 |
2024-02-08T19:02:52 Z |
vjudge1 |
Floppy (RMI20_floppy) |
C++17 |
|
81 ms |
41632 KB |
#include "floppy.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll maxn=100005;
pll sp[20][maxn];
vector <pll> euler;
ll Time, tin[maxn], L[maxn], R[maxn];
void read_array(ll subtask_id, const vector<ll> &a)
{
ll n=a.size(), root;
for (ll i=0; i<n; i++)
sp[0][i]={a[i], i};
for (ll i=1; i<20; i++)
for (ll j=0; j+(1<<i)<=n; j++)
sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
function<ll(ll, ll)> getedge=[&](ll l, ll r)
{
if (l>r) return (ll)-1;
ll j=__lg(r-l+1), pos=max(sp[j][l], sp[j][r-(1<<j)+1]).se;
L[pos]=getedge(l, pos-1), R[pos]=getedge(pos+1, r);
return pos;
}; root=getedge(0, n-1);
string ans="";
function<void(int)> dfs=[&](ll u)
{
if (L[u]==-1) ans+='0';
else ans+='1', dfs(L[u]);
if (R[u]==-1) ans+='0';
else ans+='1', dfs(R[u]);
}; dfs(root);
save_to_floppy(ans);
}
vector<ll> solve_queries(ll subtask_id, ll n, const string &s,
const vector<ll> &a, const vector<ll> &b)
{
ll crr=0, root;
for (ll i=0; i<n; i++) L[i]=R[i]=-1;
function <pll(ll)> getedge=[&](ll shift)
{
ll id=shift, cnt=1;
if (s[crr++]!='0')
{
pll res=getedge(shift);
id+=res.se, cnt+=res.se, L[id]=res.fi;
}
if (s[crr++]!='0')
{
pll res=getedge(shift+cnt);
cnt+=res.se, R[id]=res.fi;
}
return mp(id, cnt);
}; root=getedge(0).fi;
function <void(int)> dfs=[&](ll u)
{
tin[u]=euler.size();
euler.pb({tin[u], u});
if (L[u]!=-1) dfs(L[u]), euler.pb({tin[u], u});
if (R[u]!=-1) dfs(R[u]), euler.pb({tin[u], u});
}; dfs(root);
ll m=euler.size();
for (ll i=0; i<m; i++)
sp[0][i]=euler[i];
for (ll i=1; i<20; i++)
for (ll j=0; j+(1<<i)<=m; j++)
sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
auto query=[&](ll u, ll v)
{
ll l=tin[u], r=tin[v];
if (l>r) swap(l, r);
ll j=__lg(r-l+1);
return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
};
m=a.size();
vector <ll> ans(m);
for (ll i=0; i<m; i++)
ans[i]=query(a[i], b[i]);
return ans;
}
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:24:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
24 | sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
| ~^~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:75:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
75 | sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
| ~^~
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 |
4 ms |
17200 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
17200 KB |
Output is correct |
| 4 |
Correct |
3 ms |
17200 KB |
Output is correct |
| 5 |
Correct |
3 ms |
17192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
27564 KB |
Output is correct |
| 2 |
Correct |
22 ms |
27564 KB |
Output is correct |
| 3 |
Correct |
20 ms |
28504 KB |
Output is correct |
| 4 |
Correct |
23 ms |
28128 KB |
Output is correct |
| 5 |
Correct |
19 ms |
27424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
37564 KB |
Output is correct |
| 2 |
Correct |
72 ms |
37380 KB |
Output is correct |
| 3 |
Correct |
81 ms |
41632 KB |
Output is correct |
| 4 |
Correct |
74 ms |
39588 KB |
Output is correct |
| 5 |
Correct |
72 ms |
37516 KB |
Output is correct |
