제출 #1224590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224590		Sir_Ahmed_Imran	Peru (RMI20_peru)	C++17	100 / 100	591 ms	45248 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define N 2500001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int mod = 1e9 + 7;

int add(int x, int y){
    return (x + y) % mod;
}

int mul(int x, int y){
    return (1ll * x * y) % mod;
}

ll x[N];
int a[N];

int solve(int n, int k, int* v){
    int l, c, ans;
    pair<ll, pii> p;
    set<pair<ll, pii>> s;
    deque<pair<int,pii>> Q;
    for(int i = 1; i <= n; i++){
        l = i;
        a[i] = v[i - 1];
        if(!Q.empty() && Q.front().ss.ff <= i - k){
            p = Q.front();
            Q.pop_front();
            s.erase({x[p.ss.ff - 1] + p.ff, {p.ss.ff, p.ss.ss}});
            p.ss.ff++;
            if(p.ss.ff <= p.ss.ss){
                Q.push_front(p);
                s.add({x[p.ss.ff - 1] + p.ff, {p.ss.ff, p.ss.ss}});
            }
        }
        while(!Q.empty() && Q.back().ff <= a[i]){
            p = Q.back();
            s.erase({x[p.ss.ff - 1] + p.ff, {p.ss.ff, p.ss.ss}});
            Q.pop_back();
            l = p.ss.ff;
        }
        Q.append({a[i], {l, i}});
        s.add({x[l - 1] + a[i], {l, i}});
        x[i] = (*s.begin()).ff;
    } 
    c = 1;
    ans = 0;
    for(int i = n; i > 0; i--){
        x[i] %= mod;
        ans = add(ans, mul(x[i], c));
        c = mul(c, 23);
    }
    return ans;
}

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