oj.uz

Submission #401568

# Submission time Handle Problem Language Result Execution time Memory
401568 2021-05-10T13:35:44 Z Pyqe Peru (RMI20_peru) C++14
0 / 100
 0 ms 340 KB 
#include <bits/stdc++.h>
#include "peru.h"

using namespace std;

const int m=23,dv=1e9+7;
long long inf=1e18;
int nn=0,a[400069],sk[400069];
long long dp[400069];

struct segtree
{
	int l,r;
	long long mn,lz;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		mn=0;
		lz=0;
		if(l<r)
		{
			int ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void blc()
	{
		int ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mn+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(int lh,int rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn+=w;
			lz+=w;
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	long long qr(int lh,int rh)
	{
		if(l>rh||r<lh)
		{
			return inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mn;
		}
		else
		{
			blc();
			return min(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg;

int solve(int n,int d,int* aa)
{
	int i,ml=1,z=0;
	
	if(n>400000)
	{
		for(;1;);
	}
	else
	{
		return -1;
	}
	sg.bd(1,n);
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		for(;nn&&a[sk[nn]]<=a[i];nn--)
		{
			sg.ud(sk[nn-1]+1,sk[nn],a[i]-a[sk[nn]]);
		}
		nn++;
		sk[nn]=i;
		sg.ud(i,i,dp[i-1]+a[i]);
		dp[i]=sg.qr(max(i-d+1,1),i);
	}
	for(i=n;i;i--)
	{
		z=(dp[i]%dv*ml+z)%dv;
		ml=(long long)ml*m%dv;
	}
	return z;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -