Submission #657744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
657744	2022-11-10T23:14:37 Z	lovrot	Peru (RMI20_peru)	C++17	Compilation error	0 ms	0 KB

peru

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

using namespace std; 

typedef long long ll;

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

ll dp[N];

int add(int a, int b){
	if(a + b < 0) return a + b + N;
	if(a + b >= N) return a + b - N;
	return a + b;
}

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

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

struct elem{
	ll val, maxi;
	int ind;
	elem(){
		val = 0;
		maxi = 0;
		ind = 0;
	};
};

struct monostack{
	elem arr[N];
	int ind = 0;
	void push(elem x){
		if(ind) x.val = min(x.val, arr[ind - 1].val);
		arr[ind] = x;
		ind++;
	};
	elem pop(){
		if(ind){
			ind--;
			return arr[ind];
		}
		assert(false);
		return arr[ind];
	};
	elem front(){
		if(ind) return arr[ind - 1];
		assert(false);
		return arr[ind];
	};
	ll mini(){
		if(ind) return arr[ind - 1].val;
		return INF;
	}
	int size(){
		return ind;
	};
	void clear(){
		ind = 0;
	};
};

struct monodeck{
	monostack l, r;
	elem arr[N];
	int L = 0, R = 1;
	void build(){
		if(l.size() > 0 && r.size() > 0) return;
		//printf("building\n");
		int mi = (L + R) >> 1;
		if(L > R) mi = (L - N + R) >> 1;
		l.clear();
		r.clear();
		for(int i = mi; i != L; i = add(i, -1)){
			assert(i >= 0);
			l.push(arr[i]);
		} 
		for(int i = mi + 1; i != R; i = add(i, 1)){
			assert(i < N);
			r.push(arr[i]);
		} 
	}
	void push_front(elem x){
		arr[L] = x;
		l.push(x);
		L = add(L, -1);
		build();
	};
	void push_back(elem x){
		arr[R] = x;
		r.push(x);
		R = add(R, 1);
		build();
	};
	elem pop_front(){
		if(l.size() == 0) swap(l, r);
		L = add(L, 1);
		elem ret = l.pop();
		build();
		return ret;
	};
	elem pop_back(){
		if(r.size() == 0) swap(l, r);
		R = add(R, -1);
		elem ret = r.pop();
		build();
		return ret;
	};
	elem front(){
		return arr[add(L, 1)];
	};
	elem back(){
		return arr[add(R, -1)];
	};
	ll mini(){
		return min(l.mini(), r.mini());
	}
	int size(){
		return l.size() + r.size();
	};
};

ll DP(int x){
	if(x < 0) return 0;
	return dp[x];
}

int solve(int n, int k, int* arr){
	elem res, p; 
	monodeck s;
	dp[0] = arr[0];
	p.val = arr[0];
	p.maxi = arr[0];
	p.ind = 0;
	s.push_back(p);
	for(int i = 1; i < n; i++){
		if(i >= k){
			res = s.pop_front();
			//printf("ind = %d\n", res.ind);
			p.val = dp[i - k] + res.maxi;
			p.maxi = res.maxi;
			p.ind = i - k + 1;
			if(p.ind != i){
				if(s.size()){ 
					if(s.front().ind != p.ind) s.push_front(p);
				} else { 
					s.push_front(p);
				}
				//if(i == 2) printf("i = 2 ! %d\n", s.size());
			} 
		}
		bool del = false;
		while(s.size() && s.back().maxi <= arr[i]){
			res = s.pop_back();
			del = true;
		}
		//if(i == 3) printf("siz = %d maxi %lld front %d\n", s.size(), s.mini(), s.L);
		if(del){
			p.val = DP(res.ind - 1) + arr[i];
			p.maxi = arr[i];
			p.ind = res.ind;
			s.push_back(p);
			//printf("%d - diff %d\n", i, res.ind);
		} else {
			p.val = arr[i] + dp[i - 1];
			p.maxi = arr[i];
			p.ind = i;
			s.push_back(p);
			//printf("%d - same\n", i);
		}
		dp[i] = s.mini();
	}
	ll ans = 0;
	ll c = 1;
	for(int i = n - 1; i >= 0; i--){
		ans = MODadd(ans, MODmult(dp[i], c));
		c = MODmult(c, 23);
		//printf("%lld ", dp[i]);
	}
	//printf("\n");
	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 'int main()':
peru.cpp:194:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
peru.cpp:196:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |  for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccpLgowz.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwqzQvy.o:peru.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status