Submission #401540

#	Time	Username	Problem	Language	Result	Execution time	Memory
401540		puppies_and_rainbows	Peru (RMI20_peru)	C++14	100 / 100	546 ms	121364 KiB

peru

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,mmx")
#include "peru.h"
using namespace std;
#define int long long
using namespace std;

int mod=1000000007;
int n, k, a[2500005], dp[2500005], ax[2500005];
int ll=1, rr=0;
int smh[2500005];

const int N = 2500005;
int t[2 * N];

void build() 
{
  for (int i = n - 1; i > 0; --i) t[i] = 100000000000000000ll;
}

void modify(int p, int value) 
{
	// cout<<"concac "<<p<<" "<<value<<endl;  
  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = min(t[p],t[p^1]);
}

int query(int l, int r) 
{
  int res = 100000000000000000ll;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) 
  {
    if (l&1) res = min(res, t[l++]);
    if (r&1) res = min(res, t[--r]);
  }
  return res;
}

void addto(int pos)
{
	while(rr>=ll&&a[pos]>a[smh[rr]])
	{
		ax[smh[rr]]=100000000000000000ll;
		modify(smh[rr], ax[smh[rr]]);
		rr--;
	}
	if(rr>=ll)
	{
		ax[pos]=a[pos]+dp[smh[rr]];
		modify(pos, ax[pos]);
		// lol.push({-ax[pos], pos});
	}
	else
	{
		ax[pos]=a[pos]+dp[max(0ll, pos-k)];
		modify(pos, ax[pos]);
		// lol.push({-ax[pos], pos});
	}
	rr++; smh[rr]=pos;
	if(smh[ll]==pos-k)
	{
		modify(smh[ll], 100000000000000000ll);
		ll++;
	}
	else
	{
		ax[smh[ll]]=a[smh[ll]]+dp[max(0ll, pos-k)];
		modify(smh[ll], ax[smh[ll]]);
		// lol.push({-ax[smh[l]], smh[l]});
	}
}

signed solve(signed nn, signed kk, signed* bucac)
{
	n=nn, k=kk;
	build();
	for(int i=1; i<=n; i++)
	{
		a[i]=bucac[i-1];
	}
	for(int i=1; i<=n; i++)
	{
		addto(i);
		dp[i]=query(max(1ll, i-k+1), i+1);
		// cout<<i<<" cac"<<endl;
		// for(int j=max(1ll, i-k); j<=i; j++)
		// {
		// 	cout<<ax[j]<<" ";
		// }
		// cout<<endl<<dp[i]<<endl;
	}
	int dhs=1, ans=0;
	for(int i=n; i>=1; i--)
	{
		ans+=(dp[i]%mod*dhs)%mod;
		ans%=mod;
		dhs=(dhs*23)%mod;
	}
	return ans;
}

// vector<int> aa={3, 2, 9, 8, 7, 11, 3, 4};

// signed main()
// {
// 	// n=100;
// 	// build();
// 	// modify(2, 5);
// 	// modify(3, 7);
// 	// modify(4, 9);
// 	// modify(2, 7);
// 	// cout<<query(2, 5);
// 	// return 0;
// 	cout<<solve(8, 3, aa);
// }

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