oj.uz

Submission #924280

# Submission time Handle Problem Language Result Execution time Memory
924280 2024-02-08T19:02:21 Z Tuanlinh123 Floppy (RMI20_floppy) C++17
100 / 100
 80 ms 41644 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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17196 KB Output is correct
2 Correct 3 ms 17192 KB Output is correct
3 Correct 3 ms 17184 KB Output is correct
4 Correct 3 ms 17200 KB Output is correct
5 Correct 4 ms 17188 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27564 KB Output is correct
2 Correct 21 ms 27552 KB Output is correct
3 Correct 20 ms 28616 KB Output is correct
4 Correct 19 ms 28084 KB Output is correct
5 Correct 20 ms 27412 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 37452 KB Output is correct
2 Correct 73 ms 37328 KB Output is correct
3 Correct 72 ms 41644 KB Output is correct
4 Correct 72 ms 39568 KB Output is correct
5 Correct 80 ms 37328 KB Output is correct