Submission #1189450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189450		alexander707070	Fish 3 (JOI24_fish3)	C++20	100 / 100	601 ms	46944 KiB

Main

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

struct query{
    int from,id;
};


int n,l,r,q;
long long c[MAXN],D,ans[MAXN],pref[MAXN];
vector<query> qs[MAXN];

struct SegmentTree{
    long long tree[4*MAXN],lazy[4*MAXN];

    void psh(int v,long long l,long long r){
        if(lazy[v]==0)return;

        long long tt=(l+r)/2;

        tree[2*v]+=lazy[v]*(tt-l+1);
        lazy[2*v]+=lazy[v];

        tree[2*v+1]+=lazy[v]*(r-tt);
        lazy[2*v+1]+=lazy[v];

        lazy[v]=0;
    }

    void update(int v,int l,int r,int ll,int rr,long long val){
        if(ll>rr)return;

        if(l==ll and r==rr){
            tree[v]+=(long long) val*(r-l+1);
            lazy[v]+=val;

        }else{
            int tt=(l+r)/2;
            psh(v,l,r);

            update(2*v,l,tt,ll,min(tt,rr),val);
            update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

            tree[v]=tree[2*v]+tree[2*v+1];
        }
    }

    long long getsum(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr)return tree[v];

        int tt=(l+r)/2;
        psh(v,l,r);

        return getsum(2*v,l,tt,ll,min(tt,rr)) + getsum(2*v+1,tt+1,r,max(tt+1,ll),rr);
    }

    long long query(int x){
        return getsum(1,1,n,x,x);
    }
}tree;

struct union_find{
    int dsu[MAXN],sz[MAXN];
    int from[MAXN],to[MAXN];

    void init(){
        for(int i=1;i<=n;i++){
            dsu[i]=i; sz[i]=1;
            from[i]=to[i]=i;
        }
    }

    int root(int x){
        if(dsu[x]==x)return x;
        dsu[x]=root(dsu[x]);
        return dsu[x];
    }

    void mergev(int x,int y){
        int rootx=root(x);
        int rooty=root(y);

        if(rootx==rooty)return;
        if(sz[rootx]<sz[rooty])swap(rootx,rooty);
        
        dsu[rooty]=rootx;
        sz[rootx]+=sz[rooty];

        from[rootx]=min(from[rootx],from[rooty]);
        to[rootx]=max(to[rootx],to[rooty]);
    }

    pair<int,int> where(int x){
        return {from[root(x)],to[root(x)]};
    }

}segments;

long long calc(long long x){
    return x/D + (x%D!=0);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>D;

    for(int i=1;i<=n;i++){
        cin>>c[i];

        tree.update(1,1,n,i,i,c[i]);
        pref[i]=pref[i-1]+c[i];
    }

    segments.init();
    
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>l>>r;
        qs[r].push_back({l,i});
    }

    for(int i=2;i<=n;i++){
        int curr=i-1;
        
        while(curr>=1){
            long long x=tree.query(curr);
            long long y=tree.query(curr+1);

            if(y-x>=D)break;
            if(y-x>=0){
                segments.mergev(curr,curr+1);
                break;
            }

            long long tims=calc(x-y);
            auto p=segments.where(curr);

            tree.update(1,1,n,p.first,p.second,-tims*D);

            segments.mergev(curr,curr+1);
            curr=p.first-1;
        }

        for(auto e:qs[i]){
            if(tree.query(e.from)<0)ans[e.id]=-1;
            else ans[e.id]=( (pref[i]-pref[e.from-1]) - tree.getsum(1,1,n,e.from,i) )/D;
        }
    }

    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }

    return 0;
}

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