oj.uz

Submission #572266

# Submission time Handle Problem Language Result Execution time Memory
572266 2022-06-04T07:27:12 Z tarunares7250 Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 212 KB 
//ulimit -s unlimited
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define pql priority_queue<long long>
#define pqp priority_queue<pair<ll,ll> >
#define pqs priority_queue<ll,vl,greater<ll> >
#define md ((ll) 1e9+7)

vl st;
//nl node left;nr node right;ql query left;qr query right;n node key;
ll minq(ll nl,ll nr,ll ql,ll qr,ll n){
    if(qr>=nr && ql<=nl){
        return st[n];
    }
    else if(qr<nl || ql>nr){
        return md;
    }
    return min(minq(nl,(nl+nr)/2,ql,qr,2*n),minq((nl+nr)/2 + 1,nr,ql,qr,2*n+1));
}

void updateq(ll nl,ll nr,ll n,ll i,ll v){
    if(nl == nr && nl == i){
        st[n] = min(v,st[n]);
        return;
    }
    ll mid = (nl+nr)/2;
    if(i<=mid){
        updateq(nl,mid,2*n,i,v);
    }
    else{
        updateq(mid+1,nr,2*n+1,i,v);
    }
    st[n] = min(st[2*n],st[2*n+1]);
}


void solve(){

    ll i,j,k,n,m;
    cin>>n>>m;

    ll a[n+1];
    a[0] = 0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        a[i] -= i*m;
    }

    map<ll,ll> cc;
    cc[0];
    for(i=0;i<n;i++){
        cc[a[i]];
    }
    i = 0;
    for(auto &c:cc){
        c.second = i;
        i++;
    }

    k = cc.size();
    k++;
    st.resize(4*k,md);
    ll dp[n+1];

    for(i=n;i>=0;i--){
        ll ans = minq(0,k-1,0,cc[a[i]],1);
        dp[i] = ans-i-1;
        dp[i] = min(dp[i],n-i);
        updateq(0,k-1,1,cc[a[i]],dp[i]+i);
    }
    cout<<dp[0]<<"\n";


}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    //cin >> t;
    t = 1;
    while(t--)
        solve();
    return 0;
}

Compilation message

triusis.cpp: In function 'void solve()':
triusis.cpp:43:10: warning: unused variable 'j' [-Wunused-variable]
   43 |     ll i,j,k,n,m;
      |          ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -