Submission #1290361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290361		HoriaHaivas	Peru (RMI20_peru)	C++20	49 / 100	1103 ms	175564 KiB

peru

#include<bits/stdc++.h>
#include "peru.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct apdeit
{
    int l;
    int r;
    int numar;
};

int dp[2500005];
signed S[2500005];
int v[2500005];
apdeit st[2500005];///avem o stiva cu updateurile, care e defapt stiva pentru cost (elemente mai mari/mai mici)
const int mod=1e9+7;

struct Node
{
    int lazy;
    int minval;
};

class AINT
{
public:
    Node aint[10000005];

    void build(int l, int r, int val)
    {
         if (l==r)
         {
             if (l==0)
             aint[val].minval=0;
             else
             aint[val].minval=1e18;
             aint[val].lazy=0;
             return;
         }
         int mid;
         mid=(l+r)/2;
         build(l,mid,val*2);
         build(mid+1,r,val*2+1);
         aint[val].minval=1e18;
         aint[val].lazy=0;
    }

    void prop(int val, int l, int r)
    {
        if (aint[val].lazy==0)
            return;
        aint[val].minval+=aint[val].lazy;
        if (l!=r)
        {
            aint[val*2].lazy+=aint[val].lazy;
            aint[val*2+1].lazy+=aint[val].lazy;
        }
        aint[val].lazy=0;
    }

    void small_update(int l, int r, int val, int poz, int x)
    {
         prop(val,l,r);
         if (l==r && l==poz)
         {
             aint[val].minval=x;
             return;
         }
         int mid;
         mid=(l+r)/2;
         if (poz<=mid)
             small_update(l,mid,val*2,poz,x);
         else
             small_update(mid+1,r,val*2+1,poz,x);
         prop(val*2,l,mid);
         prop(val*2+1,mid+1,r);
         aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
    }

    void lazy_update(int l, int r, int val, int qa, int qb, int x)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            aint[val].lazy+=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (qa<=mid)
            lazy_update(l,mid,val*2,qa,qb,x);
        if (qb>mid)
            lazy_update(mid+1,r,val*2+1,qa,qb,x);
        prop(val*2,l,mid);
        prop(val*2+1,mid+1,r);
        aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            return aint[val].minval;
        }
        int ans,mid;
        ans=1e18;
        mid=(l+r)/2;
        if (qa<=mid)
            ans=min(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=min(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }
} aint;

int lgpow(int x, int p)
{
    int ans,pw,i;
    ans=1;
    pw=x;
    for (i=0;i<30;i++)
    {
         if (p&(1<<i))
             ans=(ans*pw)%mod;
         pw=(pw*pw)%mod;
    }
    return ans;
}

signed solve(signed N, signed K, signed* S)
{
    int n,k,i,j,ans,t;
    n=N;
    k=K;
    ans=0;
    for (i=1;i<=n;i++)
    {
         v[i]=S[i-1];
    }
    aint.build(0,n,1);
    t=0;
    st[0].l=0;
    st[0].r=0;
    st[0].numar=0;
    for (i=1;i<=n;i++)
    {
         while (t>0 && st[t].numar<=v[i])
         {
              aint.lazy_update(0,n,1,st[t].l,st[t].r-1,-st[t].numar);
              t--;
         }
         t++;
         st[t].l=st[t-1].r;
         st[t].r=i;
         st[t].numar=v[i];
         aint.lazy_update(0,n,1,st[t].l,st[t].r-1,st[t].numar);
         dp[i]=aint.query(0,n,1,max(0LL,i-k),i-1);
         aint.small_update(0,n,1,i,dp[i]);
         ans+=((dp[i]%mod)*lgpow(23,n-i))%mod;
         ans%=mod;
    }
    return ans;
}

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