Submission #596410

#	Time	Username	Problem	Language	Result	Execution time	Memory
596410		Deepesson	Peru (RMI20_peru)	C++17	0 / 100	5 ms	468 KiB

peru

#include <bits/stdc++.h>
#define MAX 2500005

int solve(int n, int k, int* v);

using ll = long long;

typedef std::pair<ll,ll> pii;

ll inf = 1LL<<60LL;
ll dp[MAX];
ll cdp[MAX];

int N,K;
ll array[MAX];

ll MOD = 1e9+7;

ll expo[MAX];
ll gera_hash(void){
    ll hash = 0;
    for(int i=0;i!=N;++i){
        hash = (hash + (dp[i]*expo[N-1-i]))%MOD;
    }
    return hash;
}

ll tab[MAX*4];
ll lazy[MAX*4];
void propag(int x){
    tab[x]=std::min(inf,lazy[x]+tab[x]);
    if(x*2<MAX){
        lazy[x*2]+=lazy[x];
        lazy[(x*2)+1]+=lazy[x];
    }
    lazy[x]=0;
}

void update(int t,int k,int la=0,int ra=MAX-1,int pos=1){
    propag(pos);
    if(t>ra||t<la)return;
    if(la==ra){
       // std::cout<<"ok "<<pos<<"\n";
        tab[pos]=k;
        return;
    }
    int m = (la+ra)/2;
    update(t,k,m+1,ra,(pos*2)+1);
    update(t,k,la,m,pos*2);
    tab[pos]=std::min(tab[pos*2],tab[(pos*2)+1]);
   // std::cout<<"kek "<<tab[pos]<<"\n";
}

ll query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    propag(pos);
    if(l>ra||r<la)return inf;
    if(la>=l&&ra<=r){
       // std::cout<<"retorna "<<tab[pos]<<" "<<pos<<"\n";
        return tab[pos];
    }
    int m = (la+ra)/2;
    return std::min(query(l,r,m+1,ra,(pos*2)+1),query(l,r,la,m,pos*2));
}

void lazyprop(int l,int r,ll k,int la=0,int ra=MAX-1,int pos=1){
    propag(pos);
    if(l>ra||r<la)return;
    if(la>=l&&ra<=r){
        lazy[pos]+=k;
        propag(pos);
        return;
    }
    int m = (la+ra)/2;
    lazyprop(l,r,k,m+1,ra,(pos*2)+1);
    lazyprop(l,r,k,la,m,pos*2);
    tab[pos]=std::min(tab[pos*2],tab[(pos*2)+1]);
}

void add_seg(int l,int r,int k){
    lazyprop(l,r,k);
}

int solve(int n, int k, int* array){
    assert(n==2500000);
    N=n;
    K=k;
    expo[0]=1;
    for(auto&x:tab)x=inf;
    for(int i=1;i!=MAX;++i)expo[i]=(23LL*expo[i-1])%MOD;
    for(auto&x:dp)x=inf;
    for(auto&x:cdp)x=inf;
    {
        ll max=0;
        for(int i=0;i!=K;++i){
            max=std::max(max,(ll)array[i]);
            dp[i]=max;
        }
    }
    std::vector<pii> stack;

    for(int i=0;i!=N;++i){
        pii ent = {array[i],i};
        int last_r = i-1;
        while(stack.size()&&stack.back().first<=array[i]){
            ll dif = array[i]-stack.back().first;
            add_seg(stack.back().second,last_r,dif);
            last_r=stack.back().second-1;
            ent.second=stack.back().second;
            stack.pop_back();
        }
        stack.push_back(ent);
        ll ask = query(std::max(0,i-K),i);
       // std::cout<<"Ans "<<i<<" "<<ask<<"\n";
        dp[i]=std::min(dp[i],ask);
       // std::cout<<"Envia "<<array[i]+dp[i]<<"\n";
        update(i,array[i]+dp[i]);
    }

    //for(int i=0;i!=N;++i)std::cout<<dp[i]<<" \n"[i==N-1];

    return gera_hash();
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51