oj.uz

Submission #574936

# Submission time Handle Problem Language Result Execution time Memory
574936 2022-06-09T13:07:25 Z urosk Floppy (RMI20_floppy) C++14
100 / 100
 146 ms 64052 KB 
#include "floppy.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define llinf 1000000005 // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 1000005
#define lg 25
ll n;
ll A[maxn];
ll t[4*maxn];
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = A[tl];
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = max(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return -llinf;
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
map<ll,ll> mp;
ll lf[maxn];
ll rf[maxn];
ll tr = 1;
void construct(ll node,ll l,ll r){
    if(l>r) return;
    if(l==r) return;
    ll i = mp[get(1,1,n,l,r)];
    lf[node] = 1;
    rf[node] = 1;
    if(l==i) lf[node] = 0;
    if(r==i) rf[node] = 0;
    if(lf[node]&&l<=i-1){tr++; construct(tr,l,i-1);}
    if(rf[node]&&i+1<=r){tr++; construct(tr,i+1,r);}
}
void read_array(int subtask_id, const std::vector<int> &v) {
    n = sz(v);
    for(ll i = 1;i<=n;i++) A[i] = v[i-1];
    for(ll i = 1;i<=n;i++) mp[A[i]] = i;
    init(1,1,n);
    string s;
    construct(1,1,n);
    for(ll i = 1;i<=n;i++){
        if(lf[i]) s.pb('1');
        else s.pb('0');
        if(rf[i]) s.pb('1');
        else s.pb('0');
    }
    save_to_floppy(s);
}
ll dp[maxn];
ll inv[maxn];
vector<ll> g[maxn];
ll st[maxn][lg];
ll it = 1;
ll in[maxn];
ll id[maxn];
ll out[maxn];
ll tim = 1;
ll f = 1;
ll x = 2;
void dfs(ll i,ll par){
    in[i] = tim++;
    st[i][0] = par;
    lf[i] = A[2*i-1];
    rf[i] = A[2*i];
    if(lf[i]!=0) lf[i] = x++;
    if(lf[i]!=0){
        dfs(lf[i],i);
    }
    id[f++] = i;
    inv[i] = f-1;
    if(rf[i]!=0) rf[i] = x++;
    if(rf[i]!=0){
        dfs(rf[i],i);
    }
    out[i] = tim - 1;
}
bool intree(ll x,ll y){return in[x]>=in[y]&&out[x]<=out[y];}
ll lca(ll x,ll y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(ll j = lg-1;j>=0;j--){
        if(!intree(x,st[y][j])) y = st[y][j];
    }
    return st[y][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) {
    n = N;
    for(ll i = 1;i<=2*n;i++) A[i] = (bits[i-1]-'0');
    dfs(1,1);
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
    vector<ll> ans;
    for(ll i = 0;i<sz(a);i++){
        ll l = a[i]+1;
        ll r = b[i]+1;
        ans.pb(inv[lca(id[l],id[r])]-1);
    }
    return ans;
}
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/

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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47948 KB Output is correct
2 Correct 30 ms 47960 KB Output is correct
3 Correct 31 ms 47816 KB Output is correct
4 Correct 27 ms 47964 KB Output is correct
5 Correct 28 ms 47952 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 51416 KB Output is correct
2 Correct 59 ms 51372 KB Output is correct
3 Correct 56 ms 51716 KB Output is correct
4 Correct 56 ms 51724 KB Output is correct
5 Correct 56 ms 51452 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 63184 KB Output is correct
2 Correct 146 ms 63168 KB Output is correct
3 Correct 130 ms 63956 KB Output is correct
4 Correct 129 ms 64052 KB Output is correct
5 Correct 138 ms 63064 KB Output is correct