oj.uz

Submission #657433

# Submission time Handle Problem Language Result Execution time Memory
657433 2022-11-09T20:26:13 Z drkarlicio2107 Peru (RMI20_peru) C++14
100 / 100
 278 ms 198708 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 [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

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 122444 KB Output is correct
2 Correct 43 ms 122404 KB Output is correct
3 Correct 46 ms 122400 KB Output is correct
4 Correct 45 ms 122392 KB Output is correct
5 Correct 52 ms 122444 KB Output is correct
6 Correct 44 ms 122392 KB Output is correct
7 Correct 45 ms 122484 KB Output is correct
8 Correct 44 ms 122464 KB Output is correct
9 Correct 47 ms 122416 KB Output is correct
10 Correct 51 ms 122444 KB Output is correct
11 Correct 43 ms 122472 KB Output is correct
12 Correct 45 ms 122396 KB Output is correct
13 Correct 47 ms 122484 KB Output is correct
14 Correct 51 ms 122444 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 122444 KB Output is correct
2 Correct 43 ms 122404 KB Output is correct
3 Correct 46 ms 122400 KB Output is correct
4 Correct 45 ms 122392 KB Output is correct
5 Correct 52 ms 122444 KB Output is correct
6 Correct 44 ms 122392 KB Output is correct
7 Correct 45 ms 122484 KB Output is correct
8 Correct 44 ms 122464 KB Output is correct
9 Correct 47 ms 122416 KB Output is correct
10 Correct 51 ms 122444 KB Output is correct
11 Correct 43 ms 122472 KB Output is correct
12 Correct 45 ms 122396 KB Output is correct
13 Correct 47 ms 122484 KB Output is correct
14 Correct 51 ms 122444 KB Output is correct
15 Correct 73 ms 130432 KB Output is correct
16 Correct 80 ms 130364 KB Output is correct
17 Correct 73 ms 130316 KB Output is correct
18 Correct 85 ms 130388 KB Output is correct
19 Correct 79 ms 130368 KB Output is correct
20 Correct 91 ms 130308 KB Output is correct
21 Correct 76 ms 130428 KB Output is correct
22 Correct 77 ms 130396 KB Output is correct
23 Correct 76 ms 130556 KB Output is correct
24 Correct 81 ms 130364 KB Output is correct
25 Correct 79 ms 130348 KB Output is correct
26 Correct 75 ms 130292 KB Output is correct
27 Correct 71 ms 130396 KB Output is correct
28 Correct 76 ms 130508 KB Output is correct
29 Correct 72 ms 130588 KB Output is correct
30 Correct 80 ms 130436 KB Output is correct
31 Correct 79 ms 130348 KB Output is correct
32 Correct 73 ms 130488 KB Output is correct
33 Correct 92 ms 130380 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 130432 KB Output is correct
2 Correct 80 ms 130364 KB Output is correct
3 Correct 73 ms 130316 KB Output is correct
4 Correct 85 ms 130388 KB Output is correct
5 Correct 79 ms 130368 KB Output is correct
6 Correct 91 ms 130308 KB Output is correct
7 Correct 76 ms 130428 KB Output is correct
8 Correct 77 ms 130396 KB Output is correct
9 Correct 76 ms 130556 KB Output is correct
10 Correct 81 ms 130364 KB Output is correct
11 Correct 79 ms 130348 KB Output is correct
12 Correct 75 ms 130292 KB Output is correct
13 Correct 71 ms 130396 KB Output is correct
14 Correct 76 ms 130508 KB Output is correct
15 Correct 72 ms 130588 KB Output is correct
16 Correct 80 ms 130436 KB Output is correct
17 Correct 79 ms 130348 KB Output is correct
18 Correct 73 ms 130488 KB Output is correct
19 Correct 92 ms 130380 KB Output is correct
20 Correct 43 ms 122444 KB Output is correct
21 Correct 43 ms 122404 KB Output is correct
22 Correct 46 ms 122400 KB Output is correct
23 Correct 45 ms 122392 KB Output is correct
24 Correct 52 ms 122444 KB Output is correct
25 Correct 44 ms 122392 KB Output is correct
26 Correct 45 ms 122484 KB Output is correct
27 Correct 44 ms 122464 KB Output is correct
28 Correct 47 ms 122416 KB Output is correct
29 Correct 51 ms 122444 KB Output is correct
30 Correct 43 ms 122472 KB Output is correct
31 Correct 45 ms 122396 KB Output is correct
32 Correct 47 ms 122484 KB Output is correct
33 Correct 51 ms 122444 KB Output is correct
34 Correct 236 ms 195112 KB Output is correct
35 Correct 239 ms 195296 KB Output is correct
36 Correct 237 ms 195216 KB Output is correct
37 Correct 235 ms 195244 KB Output is correct
38 Correct 278 ms 195248 KB Output is correct
39 Correct 227 ms 195320 KB Output is correct
40 Correct 244 ms 195376 KB Output is correct
41 Correct 246 ms 195204 KB Output is correct
42 Correct 237 ms 195424 KB Output is correct
43 Correct 133 ms 151856 KB Output is correct
44 Correct 179 ms 167152 KB Output is correct
45 Correct 175 ms 167216 KB Output is correct
46 Correct 179 ms 167176 KB Output is correct
47 Correct 231 ms 197388 KB Output is correct
48 Correct 242 ms 197516 KB Output is correct
49 Correct 245 ms 197768 KB Output is correct
50 Correct 274 ms 198412 KB Output is correct
51 Correct 237 ms 198032 KB Output is correct
52 Correct 241 ms 198708 KB Output is correct
53 Correct 239 ms 198588 KB Output is correct
54 Correct 259 ms 195328 KB Output is correct
55 Correct 259 ms 195116 KB Output is correct
56 Correct 246 ms 194940 KB Output is correct
57 Correct 242 ms 195064 KB Output is correct
58 Correct 257 ms 195132 KB Output is correct
59 Correct 245 ms 194916 KB Output is correct
60 Correct 268 ms 194992 KB Output is correct
61 Correct 269 ms 197056 KB Output is correct
62 Correct 273 ms 197096 KB Output is correct
63 Correct 267 ms 196992 KB Output is correct