Submission #1246352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246352		YassirSalama	Fish 3 (JOI24_fish3)	C++20	0 / 100	622 ms	226444 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
const int maxn = 3e5+100;
const int LOGN = 30;
int arr[maxn];
int st[maxn][LOGN];
int lg[maxn];
int up[maxn][LOGN];
int ss[maxn][LOGN];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    lg[1] = 0;
    for(int i=2;i<maxn;i++) lg[i] = lg[i>>1]+1;
    int n,d;
    cin>>n>>d;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        st[i][0] = arr[i];
    }
    for(int j = 1;j<LOGN;j++){
        for(int i = 1;i+(1LL<<j)<=n+1;i++){
            st[i][j] = min(st[i][j-1],st[i+(1LL<<(j-1))][j-1]);
        }
    }
    auto query = [&](int l,int  r){
        int k = r-l+1;
        k = lg[k];
        return min(st[l][k],st[r-(1LL<<k)+1][k]);
    };
    int pref[n+1];memset(pref,0,sizeof(pref));
    for(int i = 1;i<=n;i++){
        pref[i] = arr[i];
        if(i) pref[i]+=pref[i-1];
    }
    auto sum = [&](int l,int r){
        if(l>r) return 0LL;
        if(l==0) return pref[r];
        return pref[r]-pref[l-1];
    };
    int next[n+1];memset(next,0,sizeof(next));
    next[1] = 0;
    for(int i = 2;i<=n;i++){
        next[i] = i-1;
        while(next[i]!=0&&arr[i]<=arr[next[i]]){
            next[i] = next[next[i]];
        }
    }
    memset(up,0,sizeof(up));
    memset(ss,0,sizeof(ss));
    for(int i=1;i<=n;i++){
        int l = next[i],r = i;
        int w = 0;
        if(l==0){
            w = 0;
        }else{
            int x = arr[next[i]];
            w = -(r-l)*x;
        }
        up[i][0] = l;
        ss[i][0] = w;
    }
    for(int j = 1;j<LOGN;j++){
        for(int i=0;i<=n;i++){
            up[i][j] = up[up[i][j-1]][j-1];
            ss[i][j] = ss[i][j-1]+ss[up[i][j-1]][j-1];
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int s = sum(l,r);
        int node = r;
        int k = 0;
        for(int j = LOGN-1;j>=0;j--){
            int x = up[node][j];
            if(x<l){
                continue;
            }
            k+=ss[node][j];
            node = x;
        }
        k+=-(node-l) * arr[node];
        k+=-arr[r];
        int ans = s+k;
        cout<<ans<<endl;
    }
}

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