Submission #401509

#	Time	Username	Problem	Language	Result	Execution time	Memory
401509		Drew_	Peru (RMI20_peru)	C++14	49 / 100	653 ms	36532 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define pl pair<ll, ll>
#define f1 first
#define s2 second

const int MAX = 25e5 + 7;
const int mod = 1e9 + 7;
inline int add(ll x, ll y) { return (int)((x + y) % mod); }
inline int mul(ll x, ll y) { return (int)((x * y) % mod); }

struct Item {int mx, l, r; };

ll dp[MAX];

static int dq_l = 1, dq_r = 0;
Item dq[MAX];
int solve(int n, int k, int* v){
	priority_queue<ll, vector<ll>, greater<ll>> pq, pending;

	dp[0] = v[0];
	dq[++dq_r] = {v[0], 0, 0};
	pq.push(v[0]);

	for (int i = 1; i < n; ++i)
	{
		//remove the front
		if (dq_l <= dq_r && dq[dq_l].l <= i-k)
		{
			//int mx = dq[dq_l].mx, l = dq[dq_l].mx, r = dq[dq_l].r;
			auto [mx, l, r] = dq[dq_l];
			dq_l++;

			pending.push(mx + (l ? dp[l-1] : 0));
			if (r > i-k)
			{
				dq[--dq_l] = {mx, i-k+1, r};
				pq.push(mx + (i-k+1 ? dp[i-k] : 0));
			}
		}

		int cur_l = i, cur_r = i;
		while (dq_l <= dq_r && dq[dq_r].mx <= v[i])
		{
			//int mx = dq[dq_r].mx, l = dq[dq_r].l, r = dq[dq_r].r;
			auto [mx, l, r] = dq[dq_r];
			dq_r--;

			pending.push(mx + (l ? dp[l-1] : 0));
			cur_l = l;
		}
		dq[++dq_r] = {v[i], cur_l, cur_r};
		pq.push(v[i] + (cur_l ? dp[cur_l-1] : 0));
	
		while (!pending.empty())
		{
			if (pq.top() > pending.top())
				pending.pop();
			else if (pq.top() < pending.top())
				break;
			else pq.pop(), pending.pop();
		}

		dp[i] = pq.top();
	}

	int pwr = 1, ans = 0;
	for (int i = n-1; i >= 0; --i)
		ans = add(ans, mul(dp[i]%mod, pwr)), pwr = mul(pwr, 23);

	return ans;
}

/*
	for (int i = 0; i < n; ++i)
	{
		dp[i] = 1e18;
		
		int mx = 0;
		for (int j = i; j >= max(0, i-k+1); --j)
		{
			mx = max(mx, v[j]);
			dp[i] = min(dp[i], mx + (j ? dp[j-1] : 0));
		}
	}
*/

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:39:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |    auto [mx, l, r] = dq[dq_l];
      |         ^
peru.cpp:54:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |    auto [mx, l, r] = dq[dq_r];
      |         ^

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