Submission #657433

#	Time	Username	Problem	Language	Result	Execution time	Memory
657433		drkarlicio2107	Peru (RMI20_peru)	C++14	100 / 100	278 ms	198708 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>

using namespace std;
vector < pair <long long int, pair <long long int, long long int> > > pom;
long long int sol [2600000];

struct mono_stack {
	long long int l [2600000]; long long int ind=0;
	pair <long long int, pair <long long int, long long int> > pos [2600000];
	void push (long long int x, long long int y, long long int z){
		l [ind]=x+y;
		if (ind!=0) l [ind]=min (l [ind], l [ind-1]); 
		pos [ind]={x, {y, z}};
		ind++;
	}
	void pop (){
		l [ind-1]=0; pos [ind-1]={0, {0, 0}};
		ind--;
	}
	long long int maxi (){
		if (ind==0) return 1e18;
		return l [ind-1];
	}
	long long int size (){
		return ind;
	}
	pair <long long int, pair <long long int, long long int> > top (){
		return pos [ind-1];
	}
	pair <long long int, pair <long long int, long long int> > down (){
		return pos [0];
	}
};

struct mono_deque {
	mono_stack l; mono_stack r;
	void push_back (long long int x, long long int y, long long int z){
		l.push (x, y, z);
	}
	void push_front (long long int x, long long int y, long long int z){
		r.push (x, y, z);
	}
	void pop_back (){
		if (l.size ()!=0) l.pop();
		else {
			if (r.size()==1){
				r.pop(); return ;
			}
			pom.clear ();
			while (r.size()) {
				pom.push_back (r.top ()); r.pop();
			}
			reverse (pom.begin(), pom.end());
			for (long long int i=pom.size()/2-1; i>=0; i--) l.push (pom [i].first, pom [i].second.first, pom [i].second.second);
			for (long long int i=pom.size()/2; i<(long long int)pom.size(); i++) r.push (pom [i].first, pom [i].second.first, pom [i].second.second);
			l.pop();
		}
	}
	void pop_front(){
		if (r.size ()!=0) r.pop();
		else {
			if (l.size()==1){
				l.pop(); return ;
			}
			pom.clear ();
			while (l.size()) {
				pom.push_back (l.top ()); l.pop();
			}
			for (long long int i=pom.size()/2-1; i>=0; i--) l.push (pom [i].first, pom [i].second.first, pom [i].second.second);
			for (long long int i=pom.size()/2; i<(long long int)pom.size(); i++) r.push (pom [i].first, pom [i].second.first, pom [i].second.second);
			r.pop();
		}
	}
	long long int maxi (){
		return min (l.maxi (), r.maxi());
	}
	pair <long long int, pair <long long int, long long int> > top (){
		if (r.size()==0) return l.down ();
		return r.top();
	}
	pair <long long int, pair <long long int, long long int> > down (){
		if (l.size()==0) return r.down ();
		return l.top();
	}
	long long int size() {
		return l.size()+r.size();
	}
};

mono_deque d;
long long int t [2600000];
long long int MOD=1e9+7;

int solve (int n, int k, int *s){
	/*for (long long int i=0; i<n; i++) {
		long long int a; cin >> a;
		if (a==1){
			long long int x; cin >> x; d.push_back (x);
		}
		else if (a==2){
			long long int x; cin >> x; d.push_front (x);
		}
		else if (a==3) d.pop_back ();
		else{
			d.pop_front ();
		}
		cout << d.maxi() << endl;
	}*/
	d.push_back (0, 0, 0);
	for (long long int i=1; i<n+1; i++){
		long long int x; x=s [i-1];
		long long int maxi=1e18; long long int ind2; long long int da=0;
		while (d.size ()>0 && d.top ().second.first<=x){
			pair <long long int, pair <long long int, long long int> > z=d.top ();
			maxi=min (maxi, z.first); ind2=z.second.second;
			d.pop_front(); da=1;
		}
		if (da) d.push_front (maxi, x, ind2); 
		long long int resi, ind=-1;
		//my_sol+=x;
		while (d.size()>0 && i-k>d.down ().second.second){
			resi=d.down().second.first; ind=d.down ().second.second; d.pop_back ();
		}
		//cout << ind << endl;
		if (d.down ().second.second!=ind+1 && ind!=-1) d.push_back (sol [ind+1], resi, ind+1);
		sol [i]=d.maxi();
		//cout << d.maxi() << " " << d.size() << endl;
		d.push_front (sol [i], 0 , i); 
		//cout << sol [i] << "DA" << endl;
		
	}
	for (int i=1; i<n+1; i++) sol [i]=sol [i]%MOD;
	long long int ans=0;
	t [1]=1;
	for (long long int i=2; i<n+1; i++) t [i]=(t [i-1]*23)%MOD;
	for (long long int i=1; i<n+1; i++) ans=(ans+sol [i]*t [n-i+1])%MOD;
	//for (long long int i=1; i<n+1; i++) cout << sol [i] << " ";
	return ans;
}
/*int s [2500000];
int main (){
	long long int n, k; cin >> n >> k;
	for (int i=0; i<n; i++) cin >> s [i];
	cout << solve (n, k, s);
	return 0;
}*/

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:12:12: warning: 'resi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |   l [ind]=x+y;
      |           ~^~
peru.cpp:120:17: note: 'resi' was declared here
  120 |   long long int resi, ind=-1;
      |                 ^~~~

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