제출 #1223893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223893		lambd47	Fish 3 (JOI24_fish3)	C++20	100 / 100	618 ms	102028 KiB

Main

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

int INF=1e18;
int LG=19;

void solve() {
    int n,m;cin>>n>>m;
    INF=(INF/m)*m;
    vector<int> arr(n);
    vector<int> og;
    vector<int> pref(n);
    L(i,0,n-1){
        cin>>arr[i];
    }
    og=arr;
    int at=0;
    L(i,0,n-1){
        arr[i]-=at;
        at+=((INF+arr[i])%m);
        arr[i]-=(INF+arr[i])%m;
        arr[i]/=m;
    }
    L(i,0,n-1){
        pref[i]=arr[i];
        if(i!=0)pref[i]+=pref[i-1];
        //cout<<arr[i]<<" ";
    }
    //cout<<"\n";
    vector<int> st;
    int dp[LG][n];
    int val[LG][n];
    L(i,0,n-1){
        while(!st.empty() && arr[st.back()]>=arr[i]){
            st.pop_back();
        }
        dp[0][i]=(st.empty()?i:st.back());
        st.push_back(i);
    }
    L(i,0,n-1){
        int v=dp[0][i];
        //cout<<v<<" ";
        val[0][i]=pref[i]-pref[v]-arr[i]*(i-v);
        //cout<<val[0][i]<<"\n";
    }
    L(pot,1,LG-1){
        L(i,0,n-1){
            dp[pot][i]=dp[pot-1][dp[pot-1][i]];
            val[pot][i]=val[pot-1][i]+val[pot-1][dp[pot-1][i]];
        }
    }
    int q;cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        l--;r--;

        int at=r;
        int resp=0;

        R(pot,LG-1,0){
            if(dp[pot][at]>=l){
                resp+=val[pot][at];
                at=dp[pot][at];
            }
        }
        int pp=0;
        if(l!=0)pp=pref[l-1];
        if((arr[l]-arr[at])*m>og[l]){
            cout<<-1<<"\n";
        }
        else{
        resp+=pref[at]-pp-arr[at]*(at-l+1);
        cout<<resp<<"\n";
        }

    }






}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36