제출 #1224221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224221		Ghulam_Junaid	Peru (RMI20_peru)	C++20	0 / 100	90 ms	40200 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"
// #include "grader.cpp"
using namespace std;

const int N = 2.5e6 + 10, mod = 1e9 + 7;
int n, k, a[N], p[N], ngl[N];

int solve(int nn, int kk, int* v){
    n = nn, k = kk;
    for (int i = 1; i <= n; i ++)
        a[i] = v[i - 1];

    stack<int> st;
    st.push(0);
    for (int i = 1; i <= n; i ++){
        while (!st.empty() and st.top() != 0 and a[st.top()] <= a[i])
            st.pop();
        ngl[i] = st.top();
        st.push(i);
    }

    deque<int> dq1, dq2;
    dq1.push_back(0); dq2.push_back(0);
    for (int i = 1; i <= n; i ++){
        while (!dq1.empty() and a[dq1.back()] <= a[i]){
            if (!dq2.empty() and dq2.back() == dq1.back())
                dq2.pop_back();
            dq1.pop_back();
        }
        if (!dq1.empty() and dq1[0] <= i - k){
            if (!dq2.empty() and dq2[0] == dq1[0])
                dq2.pop_front();
            dq1.pop_front();
        }

        dq1.push_back(i);
        while (1){
            if (dq2.empty()) break;
            int j = dq2.back();
            if (p[max(i - k, ngl[j])] + a[j] <= p[max(i - k, ngl[i])] + a[i]) break;
            dq2.pop_back();
        }
        dq2.push_back(i);

        if (dq2.size() > 1 and (p[max(i - k, ngl[dq2[0]])] + a[dq2[0]] > p[max(i - k, ngl[dq2[1]])] + a[dq2[1]]))
            dq2.pop_front();
        if (dq2.front() != dq1.front() and (p[max(i - k, ngl[dq2[0]])] + a[dq2[0]] > p[max(i - k, ngl[dq1[0]])] + a[dq1[0]]))
            dq2.push_front(dq1[0]);

        p[i] = p[max(i - k, ngl[dq2[0]])] + a[dq2[0]];
    }

    int pw = 1, res = 0;
    for (int i = n; i > 0; i --, pw = (23ll * pw) % mod)
        res = (res + (1ll * p[i] * pw % mod)) % mod;
    return res;
}

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