제출 #1295934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295934		jahongir	Peru (RMI20_peru)	C++20	49 / 100	340 ms	29972 KiB

peru

#include "peru.h"

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

#define ll long long

const int mod = 1e9+7;
const ll inf = 1e18;
ll st[1<<20], lz[1<<20];

void push(int i){
    if(lz[i]!=0){
        st[i<<1|1] += lz[i], lz[i<<1|1] += lz[i];
        st[i<<1] += lz[i], lz[i<<1] += lz[i]; lz[i] = 0;
    }
}

void update(int i, int l, int r, int s, int e, ll val){
    if(r < s || l > e) return;
    if(s <= l && r <= e){
        st[i] += val; lz[i] += val; return;
    }
    push(i); int m = (l+r)>>1;
    update(i<<1,l,m,s,e,val);
    update(i<<1|1,m+1,r,s,e,val);
    st[i] = min(st[i<<1],st[i<<1|1]);
}

void add(int i, int l, int r, int k, ll val){
    if(l==r){st[i]=val; return;}
    push(i); int m = (l+r)>>1;
    if(k <= m) add(i<<1,l,m,k,val);
    else add(i<<1|1,m+1,r,k,val);
    st[i] = min(st[i<<1],st[i<<1|1]);
}

ll get(int i, int l, int r, int s, int e){
    if(r < s || l > e) return inf;
    if(s <= l && r <= e) return st[i];
    push(i); int m = (l+r)>>1;
    return min(get(i<<1,l,m,s,e),get(i<<1|1,m+1,r,s,e));
}


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

    vector<ll> dp(N+1,0);
    vector<int> sta = {0};
    
    for(int i = 1; i <= N; i++){
        while(S[sta.back()] <= S[i]){
            int r = sta.back(); sta.pop_back();
            int l = sta.back();
            update(1,1,N,l+1,r,-S[r]);
        }
        update(1,1,N,sta.back()+1,i,S[i]);

        dp[i] = get(1,1,N,max(1,i-K+1),i);
        if(i < N) add(1,1,N,i+1,dp[i]);

        sta.push_back(i);
    }

    int ans = 0, mtp = 1;
    for(int i = N; i; i--){
        ans += (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: 0 / 51