Submission #1295970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295970		jahongir	Peru (RMI20_peru)	C++20	100 / 100	99 ms	31552 KiB

peru

#include "peru.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll inf = 1e18;
const int mod = 1e9+7;

struct Stack {
	stack<pair<ll, ll>> st;
	ll getmin() {return st.top().second;}
	bool empty() {return st.empty();}
	int size() {return st.size();}
	void push(ll x) {
		ll mn = x;
		if (!empty()) mn = min(mn, getmin());
		st.push({x, mn});
	}
	void pop() {st.pop();}
	ll top() {return st.top().first;}
	void swap(Stack &x) {st.swap(x.st);}
};

struct Deque{
    Stack l, r, t;
	void rebalance() {
		bool f = false;
		if (r.empty()) {f = true; l.swap(r);}
		int sz = r.size() / 2;
		while (sz--) {t.push(r.top()); r.pop();}
		while (!r.empty()) {l.push(r.top()); r.pop();}
		while (!t.empty()) {r.push(t.top()); t.pop();}
		if (f) l.swap(r);
	}
    ll getmin() {
		if (l.empty()) return r.getmin();
		if (r.empty()) return l.getmin();
		return min(l.getmin(), r.getmin());
	}
    bool empty() {return l.empty() && r.empty();}
	int size() {return l.size() + r.size();}
	void push_front(ll x) {l.push(x);}
	void push_back(ll x) {r.push(x);}
	void pop_front() {if (l.empty()) rebalance(); l.pop();}
	void pop_back() {if (r.empty()) rebalance(); r.pop();}
	ll front() {if (l.empty()) rebalance(); return l.top();}
	ll back() {if (r.empty()) rebalance(); return r.top();}
	void swap(Deque &x) {l.swap(x.l); r.swap(x.r);}
};





int solve(int N, int K, int* S){
    for(int i = N; i; i--) S[i] = S[i-1];
    S[0] = 0;

    vector<ll> dp(N+1,0);
    deque<int> dq;
    Deque st;

    dp[1] = S[1];
    dq.push_back(1);
    st.push_back(dp[1]);

    for(int i = 2; i <= N; i++){
        int j = dq.front(); 
        dq.pop_front(); st.pop_front();

        if(j != i-K){
            dq.push_front(j);
            st.push_front(dp[max(0,i-K)] + S[j]);
        }

        while(!dq.empty() && S[dq.back()] <= S[i]){
            dq.pop_back(); st.pop_back();
        }

        if(dq.empty()){
            dq.push_back(i);
            st.push_back(dp[max(0,i-K)]+S[i]);
        }else{
            st.push_back(dp[dq.back()]+S[i]);
            dq.push_back(i);
        }     

        dp[i] = st.getmin();
    }

    int ans = 0, mtp = 1;
    for(int i = N; i; i--){
        ans += 1ll*(dp[i]%mod)*mtp%mod;
        if(ans >= mod) ans -= mod;
        mtp = 1ll*mtp*23%mod;
    }


    return ans;
}

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