oj.uz

Submission #657432

# Submission time Handle Problem Language Result Execution time Memory
657432 2022-11-09T20:25:16 Z drkarlicio2107 Peru (RMI20_peru) C++14
49 / 100
 410 ms 262144 KB 
#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 [2500000];

struct mono_stack {
	long long int l [2500000]; long long int ind=0;
	pair <long long int, pair <long long int, long long int> > pos [2500000];
	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 [2500000];
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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 117708 KB Output is correct
2 Correct 43 ms 117708 KB Output is correct
3 Correct 46 ms 117772 KB Output is correct
4 Correct 45 ms 117784 KB Output is correct
5 Correct 44 ms 117832 KB Output is correct
6 Correct 43 ms 117708 KB Output is correct
7 Correct 43 ms 117752 KB Output is correct
8 Correct 45 ms 117708 KB Output is correct
9 Correct 47 ms 117708 KB Output is correct
10 Correct 48 ms 117740 KB Output is correct
11 Correct 55 ms 117716 KB Output is correct
12 Correct 45 ms 117716 KB Output is correct
13 Correct 45 ms 117720 KB Output is correct
14 Correct 45 ms 117728 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 117708 KB Output is correct
2 Correct 43 ms 117708 KB Output is correct
3 Correct 46 ms 117772 KB Output is correct
4 Correct 45 ms 117784 KB Output is correct
5 Correct 44 ms 117832 KB Output is correct
6 Correct 43 ms 117708 KB Output is correct
7 Correct 43 ms 117752 KB Output is correct
8 Correct 45 ms 117708 KB Output is correct
9 Correct 47 ms 117708 KB Output is correct
10 Correct 48 ms 117740 KB Output is correct
11 Correct 55 ms 117716 KB Output is correct
12 Correct 45 ms 117716 KB Output is correct
13 Correct 45 ms 117720 KB Output is correct
14 Correct 45 ms 117728 KB Output is correct
15 Correct 74 ms 129888 KB Output is correct
16 Correct 83 ms 129860 KB Output is correct
17 Correct 75 ms 129832 KB Output is correct
18 Correct 77 ms 129684 KB Output is correct
19 Correct 83 ms 129792 KB Output is correct
20 Correct 80 ms 129720 KB Output is correct
21 Correct 88 ms 129740 KB Output is correct
22 Correct 72 ms 129812 KB Output is correct
23 Correct 74 ms 129944 KB Output is correct
24 Correct 79 ms 129748 KB Output is correct
25 Correct 76 ms 129808 KB Output is correct
26 Correct 80 ms 129808 KB Output is correct
27 Correct 74 ms 129792 KB Output is correct
28 Correct 75 ms 129844 KB Output is correct
29 Correct 76 ms 130016 KB Output is correct
30 Correct 85 ms 129752 KB Output is correct
31 Correct 79 ms 129740 KB Output is correct
32 Correct 74 ms 129980 KB Output is correct
33 Correct 76 ms 129792 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 129888 KB Output is correct
2 Correct 83 ms 129860 KB Output is correct
3 Correct 75 ms 129832 KB Output is correct
4 Correct 77 ms 129684 KB Output is correct
5 Correct 83 ms 129792 KB Output is correct
6 Correct 80 ms 129720 KB Output is correct
7 Correct 88 ms 129740 KB Output is correct
8 Correct 72 ms 129812 KB Output is correct
9 Correct 74 ms 129944 KB Output is correct
10 Correct 79 ms 129748 KB Output is correct
11 Correct 76 ms 129808 KB Output is correct
12 Correct 80 ms 129808 KB Output is correct
13 Correct 74 ms 129792 KB Output is correct
14 Correct 75 ms 129844 KB Output is correct
15 Correct 76 ms 130016 KB Output is correct
16 Correct 85 ms 129752 KB Output is correct
17 Correct 79 ms 129740 KB Output is correct
18 Correct 74 ms 129980 KB Output is correct
19 Correct 76 ms 129792 KB Output is correct
20 Correct 43 ms 117708 KB Output is correct
21 Correct 43 ms 117708 KB Output is correct
22 Correct 46 ms 117772 KB Output is correct
23 Correct 45 ms 117784 KB Output is correct
24 Correct 44 ms 117832 KB Output is correct
25 Correct 43 ms 117708 KB Output is correct
26 Correct 43 ms 117752 KB Output is correct
27 Correct 45 ms 117708 KB Output is correct
28 Correct 47 ms 117708 KB Output is correct
29 Correct 48 ms 117740 KB Output is correct
30 Correct 55 ms 117716 KB Output is correct
31 Correct 45 ms 117716 KB Output is correct
32 Correct 45 ms 117720 KB Output is correct
33 Correct 45 ms 117728 KB Output is correct
34 Runtime error 410 ms 262144 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -