Submission #1078052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078052		ASN49K	Peru (RMI20_peru)	C++14	49 / 100	1092 ms	185172 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
#define  int long long
using namespace std;
using i64=long long;
const i64 INF=1e18;
const i64 inf=1e9;
const int mod=1e9+7;
const int BASE=23;
int lsb(int x)
{
    return x&(-x);
}
int add(int x,int y)
{
    return (x+y)%mod;
}
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
struct Aint
{
    int n;
    vector<i64>aint,lazy;
    void init(int n)
    {
        this->n=n;
        int aint_size=n;
        while(aint_size!=lsb(aint_size))
        {
            aint_size+=lsb(aint_size);
        }
        aint_size<<=1;
        aint.assign(aint_size+1 , 0);
        lazy.assign(aint_size+1 , 0);
    }
    void add(int nod,i64 val)
    {
        aint[nod]+=val;
        lazy[nod]+=val;
    }
    void push_down(int nod)
    {
        add(nod<<1 , lazy[nod]);
        add(nod<<1|1 , lazy[nod]);
        lazy[nod]=0;
    }
    void update(int nod,int st,int dr,int l,int r,int val) {
        if (st > r || dr < l) {
            return;
        }
        if (l <= st && dr <= r)
        {
            add(nod , val);
            return;
        }
        push_down(nod);
        int m=(st+dr)/2;
        update(nod<<1,st,m,l,r,val);
        update(nod<<1|1,m+1,dr,l,r,val);
        aint[nod]=min(aint[nod<<1] , aint[nod<<1|1]);
    }
    i64 query(int nod,int st,int dr,int l,int r)
    {
        if (st > r || dr < l) {
            return INF;
        }
        if (l <= st && dr <= r)
        {
            return aint[nod];
        }
        push_down(nod);
        int m=(st+dr)/2;
        return min(query(nod<<1,st,m,l,r) , query(nod<<1|1,m+1,dr,l,r));
    }
};
signed solve(signed n, signed k, signed* v)
{
    vector<int>a(n+2 , 2*inf+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
    }

    stack<int>sk;
    sk.push(0);
    Aint dp;
    dp.init(n+1);
    dp.update(1,0,n,0,0,a[1]);

    int rez=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i]>=a[sk.top()])
        {
            int r=sk.top()-1;
            sk.pop();
            int l=sk.top();
            dp.update(1,0,n,l,r,a[i]-a[r+1]);
        }
        i64 val=dp.query(1,0,n,max(i-k , 0LL),i-1);
        rez=prod(rez , BASE);
        rez=add(rez , val%mod);
        dp.update(1,0,n,i,i,val+a[i+1]);
        sk.push(i);
    }
    return rez;
}

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