Submission #657802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
657802	2022-11-11T08:35:04 Z	lovrot	Peru (RMI20_peru)	C++17	Compilation error	0 ms	0 KB

peru

#include <bits/stdc++.h> 

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll INF = 1e18;
const int N = 25e5 + 10;
const int MOD = 1e9 + 7;

struct obj{
	ll sum;
	int arr;
	int ind; 
};

ll dp[N];
deque<obj> d;
stack<ll> l, r;

int add(ll a, ll b){
	return (a + b) % MOD;
}

int mult(ll a, ll b){
	return a * b % MOD;
}

ll opt(){
	ll ret = INF;
	if(!l.empty()) ret = min(ret, l.top());
	if(!r.empty()) ret = min(ret, r.top());
	return ret;
}

void push(stack<ll> &s, ll val){
	if(s.empty()) s.push(val);
	else s.push(min(val, s.top()));
}

void build(){
	while(!l.empty()) l.pop();
	while(!r.empty()) r.pop();
	int m = d.size() / 2;

	vector<obj> v;
	for(int i = 0; i < m; i++){
		v.push_back(d.front());
		d.pop_front();
	}
	while(!v.empty()){
		push(l, v.back().sum);
		d.push_front(v.back());
		v.pop_back();
	}
	for(int i = 0; i < d.size() - m; i++){
		v.push_back(d.back());
		d.pop_back();
	}
	while(!v.empty()){
		push(r, v.back().sum);
		d.push_back(v.back());
		v.pop_back();
	}
}	

obj getobj(ll sum, int arr, int ind){
	obj ret;
	ret.sum = sum;
	ret.arr = arr;
	ret.ind = ind;
	return ret;
}

int solve(int n, int k, int* arr){
	for(int i = 1; i <= n; i++){
		if(i == 1){
			dp[i] = arr[i - 1];
			d.push_back(getobj(dp[i - 1] + arr[i - 1], arr[i - 1], i));
			push(r, dp[i - 1] + arr[i - 1]);
		} else {
			ll dpind = i;
			while(!d.empty() && d.back().arr <= arr[i - 1]){
				dpind = d.back().ind;			
	
				d.pop_back();
				if(r.empty()) build();
				else r.pop();
			}
			d.push_back(getobj(dp[dpind - 1] + arr[i - 1], arr[i - 1], dpind));
			push(r, dp[dpind - 1] + arr[i - 1]);
			
			if(i > k){
				ll arrmax = d.front().arr;
				if(d.front().ind <= i - k){
					d.pop_front();
					if(l.empty()) build();
					else l.pop();
					
					if(d.empty()){
						d.push_front(getobj(dp[i - k] + arrmax, arrmax, i - k + 1));
						push(l, dp[i - k] + arrmax);
					} else if(d.front().ind > i - k + 1){
						d.push_front(getobj(dp[i - k] + arrmax, arrmax, i - k + 1));
						push(l, dp[i - k] + arrmax);
					}
				}
			}
			dp[i] = opt();
			//printf("dp[%d] = %lld\n", i, dp[i]);
		}
	}
		
	int ans = 0, m = 1;
	for(int i = n; i > 0; i--){
		ans = add(ans, mult(dp[i], m));
		m = mult(m, 23);
	}
	return ans;
}

int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	int arr[n];
	for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
	printf("%d\n", solve(n, k, arr));	
	return 0;
}

Compilation message

peru.cpp: In function 'void build()':
peru.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < d.size() - m; i++){
      |                 ~~^~~~~~~~~~~~~~
peru.cpp: In function 'int main()':
peru.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
peru.cpp:130:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccWgkRAi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvgzRji.o:peru.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status