Submission #1143454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143454		AlgorithmWarrior	Fish 3 (JOI24_fish3)	C++20	100 / 100	571 ms	49088 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=3e5+5;
int n,q;
long long delta;
long long cost[MAX];
long long spcost[MAX];
long long answer[MAX];

struct query{
    int l,r,ind;
    bool operator<(query ot){
        return r<ot.r;
    }
}qry[MAX];

struct node{
    long long sum,lazy;
};

struct AINT{
    node v[4*MAX];
    void propagate(int nod,int st,int dr){
        if(v[nod].lazy){
            int mij=(st+dr)/2;
            v[2*nod].sum+=v[nod].lazy*(mij-st+1);
            v[2*nod].lazy+=v[nod].lazy;
            v[2*nod+1].sum+=v[nod].lazy*(dr-mij);
            v[2*nod+1].lazy+=v[nod].lazy;
            v[nod].lazy=0;
        }
    }
    void combine(int nod){
        v[nod].sum=v[2*nod].sum+v[2*nod+1].sum;
    }
    void update(int nod,int st,int dr,int a,int b,long long delta){
        if(a<=st && dr<=b){
            v[nod].sum+=delta*(dr-st+1);
            v[nod].lazy+=delta;
        }
        else{
            propagate(nod,st,dr);
            int mij=(st+dr)/2;
            if(a<=mij)
                update(2*nod,st,mij,a,b,delta);
            if(b>mij)
                update(2*nod+1,mij+1,dr,a,b,delta);
            combine(nod);
        }
    }
    long long get_sum(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod].sum;
        propagate(nod,st,dr);
        int mij=(st+dr)/2;
        long long sum=0;
        if(a<=mij)
            sum+=get_sum(2*nod,st,mij,a,b);
        if(b>mij)
            sum+=get_sum(2*nod+1,mij+1,dr,a,b);
        return sum;
    }
    int get_last_nonzero(int nod,int st,int dr){
        if(st==dr)
            return st;
        propagate(nod,st,dr);
        int mij=(st+dr)/2;
        if(v[2*nod+1].sum>0)
            return get_last_nonzero(2*nod+1,mij+1,dr);
        return get_last_nonzero(2*nod,st,mij);
    }
}aintSum,aintDif;

void read(){
    cin>>n>>delta;
    int i;
    for(i=1;i<=n;++i){
        cin>>cost[i];
        spcost[i]=cost[i]+spcost[i-1];
    }
    cin>>q;
    for(i=1;i<=q;++i){
        cin>>qry[i].l>>qry[i].r;
        qry[i].ind=i;
    }
    sort(qry+1,qry+q+1);
}

void solve(){
    int i;
    int idq=1;
    for(i=1;i<=n;++i){
        if(cost[i]>=cost[i-1]){
            if(i>1)
                aintDif.update(1,1,n,i,i,(cost[i]-cost[i-1])/delta);
        }
        else{
            long long lvl=(cost[i-1]-cost[i]+delta-1)/delta;
            int last_pos=i;
            while(lvl && aintDif.v[1].sum){
                int pos=aintDif.get_last_nonzero(1,1,n);
                aintSum.update(1,1,n,pos,last_pos-1,-lvl*delta);
                long long sum=aintDif.get_sum(1,1,n,pos,pos);
                long long scad=min(sum,lvl);
                lvl-=scad;
                aintDif.update(1,1,n,pos,pos,-scad);
                last_pos=pos;
            }
            if(lvl)
                aintSum.update(1,1,n,1,last_pos-1,-lvl*delta);
        }
        aintSum.update(1,1,n,i,i,cost[i]);
        while(idq<=q && qry[idq].r==i){
            auto [l,r,ind]=qry[idq];
            if(aintSum.get_sum(1,1,n,l,l)<0)
                answer[ind]=-1;
            else
                answer[ind]=(spcost[r]-spcost[l-1]-aintSum.get_sum(1,1,n,l,r))/delta;
            ++idq;
        }
    }
}

void print_vector(){
    int i;
    for(i=1;i<=q;++i)
        cout<<answer[i]<<'\n';
}

int main()
{
    read();
    solve();
    print_vector();
    return 0;
}

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