Submission #1224226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224226		MuhammadSaram	Peru (RMI20_peru)	C++20	49 / 100	1073 ms	77004 KiB

peru

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 25e5, mod = 1e9 + 7;
const ll inf = 1e17;

ll seg[M*2],val[M*2],dp[M];
int n;

int power(int a,int b)
{
	int ans=1;
	for (;b;b>>=1,a=1ll*a*a%mod)
		if (b&1) ans=1ll*ans*a%mod;
	return ans;
}

void modify(int l,int r,ll x,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		val[v]+=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=min(seg[lc]+val[lc],seg[rc]+val[rc]);
}

int solve(int N,int k,int* a)
{
	n=N;
	for (int i=0;i<2*n;i++) seg[i]=inf;
	int mx=0;
	for (int i=0;i<k;i++)
		mx=max(mx,a[i]),dp[i]=mx;
	set<pair<int,int>> se;
	se.insert({0,0});
	for (int i=0;i<n;i++)
	{
		int prv=i+1;
		while (!se.empty())
		{
			pair<int,int> p=*se.rbegin();
			if (p.second>=a[i]) break;
			modify(p.first,prv,a[i]-p.second);
			prv=p.first;
			se.erase(p);
		}
		if (i>=k)
		{
			modify(i-k,i-k+1,inf);
			dp[i]=seg[0]+val[0];
		}
		if (i!=n-1)
			modify(i+1,i+2,dp[i]-inf);
		se.insert({prv,a[i]});
		se.insert({i+1,0});
	}
	int inv=power(23,mod-2),val=1,ans=0;
	for (int i=0;i<n-1;i++) val=1ll*val*23%mod;
	for (int i=0;i<n;i++,val=1ll*val*inv%mod)
		ans=(ans+dp[i]%mod*val%mod)%mod;
	return ans;
}

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