Submission #478415

#	Time	Username	Problem	Language	Result	Execution time	Memory
478415		stefantaga	Peru (RMI20_peru)	C++14	49 / 100	1095 ms	96708 KiB

peru

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
#define ll long long
ifstream f("peru.in");
ofstream g("peru.out");
long long din[2500005];
long long min1(long long a,long long b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
long long max1(long long a,long long b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
long long arb[10000005];
long long lazy[10000005];
void propaga(int st,int dr,int nod)
{
    if (st==dr)
    {
        return;
    }
    if (lazy[nod]==0)
    {
        return;
    }
    lazy[2*nod]+=lazy[nod];lazy[2*nod+1]+=lazy[nod];
    arb[2*nod]+=lazy[nod];arb[2*nod+1]+=lazy[nod];
    lazy[nod]=0;
    return;
}
void update(int st ,int dr,int nod,int ua,int ub, long long val)
{
    propaga(st,dr,nod);
    if (ua<=st&&dr<=ub)
    {
        arb[nod]+=val;
        lazy[nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        update(st,mij,2*nod,ua,ub,val);
    }
    if (mij<ub)
    {
        update(mij+1,dr,2*nod+1,ua,ub,val);
    }
    arb[nod]=min1(arb[2*nod],arb[2*nod+1]);
}
long long query(int st,int dr,int nod,int ua,int ub)
{
    propaga(st,dr,nod);
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int mij=(st+dr)/2;
    if (ub<=mij)
    {
        return query(st,mij,2*nod,ua,ub);
    }
    else
    if (mij<ua)
    {
        return query(mij+1,dr,2*nod+1,ua,ub);
    }
    else
    {
        return min1(query(st,mij,2*nod,ua,ub),query(mij+1,dr,2*nod+1,ua,ub));
    }
}
stack <int> st;
deque <pair <int,int> > maxime;
int stanga[2500005];
int solve(int n, int k, int* v)
{
    long long put=1,maxim,i,j,suma=0,ceaules;
    din[1]=v[0];
    update(1,n,1,1,1,v[0]);
    maxime.push_back({1,1});
    for (i=2;i<=n;i++)
    {
        if (maxime.front().first<i-k+1)
        {
            maxime.front().first++;
            if (maxime.front().first>maxime.front().second)
            {
                maxime.pop_front();
            }
        }
        int acum=i;
        while (!maxime.empty()&&v[maxime.back().second-1]<v[i-1])
        {
            acum=maxime.back().first;
            update(1,n,1,maxime.back().first,maxime.back().second,v[i-1]-v[maxime.back().second-1]);
            maxime.pop_back();
        }
        update(1,n,1,i,i,din[i-1]+v[i-1]);
        maxime.push_back({acum,i});
        int lim=max1(1,i-k+1);
        din[i]=query(1,n,1,lim,i);
    }
    for (i=n-1; i>=0; i--)
    {
        suma=(suma+(1LL*put*(din[i+1]%MOD))%MOD)%MOD;
        put=(1LL*23*put)%MOD;
    }
    return suma;
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:88:21: warning: unused variable 'maxim' [-Wunused-variable]
   88 |     long long put=1,maxim,i,j,suma=0,ceaules;
      |                     ^~~~~
peru.cpp:88:29: warning: unused variable 'j' [-Wunused-variable]
   88 |     long long put=1,maxim,i,j,suma=0,ceaules;
      |                             ^
peru.cpp:88:38: warning: unused variable 'ceaules' [-Wunused-variable]
   88 |     long long put=1,maxim,i,j,suma=0,ceaules;
      |                                      ^~~~~~~

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