Submission #665422

#	Time	Username	Problem	Language	Result	Execution time	Memory
665422		jcelin	Peru (RMI20_peru)	C++14	100 / 100	146 ms	31412 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 3e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

ll dp[MAXN];
stack<ll> l, r;

struct node{
	ll opt;
	int arr, ind;
	
	node(ll opt, int arr, int ind){
		this->opt = opt;
		this->arr = arr;
		this->ind = ind;
	}
};

deque<node> d;

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

int mul(ll a, ll b){
	return (a * b) % mod;
}

ll get_min(){
	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 rebuild(){
	while(!l.empty()) l.pop();
	while(!r.empty()) r.pop();
	int sz = d.size();
	int line = sz / 2;
	
	vector<node> v;
	REP(i, line) v.PB(d.front()), d.PPF();
	while(!v.empty()){
		push(l, v.back().opt);
		d.PF(v.back());
		v.PPB();
	}
	
	REP(i, sz - line) v.PB(d.back()), d.PPB();
	while(!v.empty()){
		push(r, v.back().opt);
		d.PB(v.back());
		v.PPB();
	}
}


int solve(int n, int k, int *arr){
	int ret = 0;
	for(int i = 1; i <= n; i++){
		if(i == 1){
			dp[i] = arr[i - 1];
			d.PB(node(dp[i], arr[i - 1], i));
			push(r, arr[i - 1]);
			ret = add(mul(ret, 23), dp[i]);
			continue;
		}
		
		//prvi veci u stacku(1 indeks.)
		int dpind = i;
		while(!d.empty() and d.back().arr <= arr[i - 1]){
			dpind = d.back().ind;			
			d.PPB();
			if(r.empty()) rebuild();
			else r.pop();
		}
		
		d.PB(node(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;
			
			d.pop_front();
			if(l.empty()) rebuild();
			else l.pop();
			
			//ak sam popo maksimum i maks je zadni ubacen
			if(d.empty()){
				d.push_front(node(dp[i - k] + arrmax, arrmax, i - k + 1));
				push(l, dp[i - k] + arrmax);
			}else if(d.front().ind > i - k + 1){
				//ako onaj kojeg sam popo nije najlijeviji ga vrati nazad
				d.push_front(node(dp[i - k] + arrmax, arrmax, i - k + 1));
				push(l, dp[i - k] + arrmax);
			}
			
		}
		dp[i] = get_min();
		//cout << dp[i] << " ";
		ret = add(mul(ret, 23), dp[i]);
	}
	return ret;
}

/*


void solv(){
	int n, k;
	cin >> n >> k;
	vi arr; arr.clear();
	REP(i, n){
		int x;
		cin >> x;
		arr.PB(x);
	}
	
	cout << solve(n, k, arr);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solv();
	return 0;
}


*/

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