Submission #596438

#	Time	Username	Problem	Language	Result	Execution time	Memory
596438		Deepesson	Peru (RMI20_peru)	C++17	0 / 100	78 ms	137384 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]%MOD)*expo[N-1-i]))%MOD;
    }
    return hash;
}

ll t[MAX*4];
ll d[MAX*4];
ll h = sizeof(ll) * 8 - __builtin_clz(MAX);

void update(ll p, const ll value) {
  for (t[p += MAX] = value; p >>= 1; ) t[p] = std::min(t[p<<1], t[p<<1|1]);
}

void apply(int p, ll value) {
  t[p] = std::min(inf,value+t[p]);
  if (p < MAX) d[p] += value;
}

void push(ll p) {
  for (int s = h; s > 0; --s) {
    ll i = p >> s;
    if (d[i] != 0) {
      apply(i<<1, d[i]);
      apply(i<<1|1, d[i]);
      d[i] = 0;
    }
  }
}

void build(ll p) {
  while (p > 1) p >>= 1, t[p] = std::min(t[p<<1], t[p<<1|1]) + d[p];
}

void inc(int l, int r, ll value) {
  l += MAX, r += MAX;
  ll l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) apply(l++, value);
    if (r&1) apply(--r, value);
  }
  build(l0);
  build(r0 - 1);
}

ll query(int l, int r) {
  l += MAX, r += MAX;
  push(l);
  push(r - 1);
  ll res =  inf;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = std::min(res, t[l++]);
    if (r&1) res = std::min(t[--r], res);
  }
  return res;
}

void add_seg(int l,int r,ll k){
    inc(l,r+1,k);
}

int solve(int n, int k, int* array){
    N=n;
    K=k;
    expo[0]=1;
    for(auto&x:t)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)std::cout<<dp[i]<<" \n"[i==N-1];

    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);
            //std::cout<<"update "<<stack.back().second<<" "<<last_r<<" "<<dif<<"!\n";
            last_r=stack.back().second-1;
            ent.second=stack.back().second;
            stack.pop_back();
        }
       // ent.second=std::max(ent.second,(ll)i-K);
        stack.push_back(ent);
        ll ask = query(std::max(0,i-K),i+1);
        //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