Submission #990854

#	Time	Username	Problem	Language	Result	Execution time	Memory
990854		Pacybwoah	Fish 3 (JOI24_fish3)	C++17	100 / 100	368 ms	59320 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
struct node{
    ll val=0,tag=0;
};
vector<ll> vec;
vector<node> seg;
void build(int l,int r,int ind){
    if(l==r){
        seg[ind].val=vec[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ind*2);
    build(mid+1,r,ind*2+1);
    seg[ind].val=seg[ind*2].val+seg[ind*2+1].val;
}
void push(int l,int r,int ind){
    if(l==r) return;
    int mid=(l+r)>>1;
    seg[ind*2].val+=seg[ind].tag*(mid-l+1);
    seg[ind*2+1].val+=seg[ind].tag*(r-mid);
    seg[ind*2].tag+=seg[ind].tag;
    seg[ind*2+1].tag+=seg[ind].tag;
    seg[ind].tag=0;
}
void modify(int l,int r,int start,int end,ll num,int ind){
    if(r<start||end<l) return;
    if(start<=l&&r<=end){
        seg[ind].val+=num*(r-l+1);
        seg[ind].tag+=num;
        return;
    }
    push(l,r,ind);
    int mid=(l+r)>>1;
    modify(l,mid,start,end,num,ind*2);
    modify(mid+1,r,start,end,num,ind*2+1);
    seg[ind].val=seg[ind*2].val+seg[ind*2+1].val;
}
ll query(int l,int r,int start,int end,int ind){
    if(r<start||end<l) return 0;
    if(start<=l&&r<=end) return seg[ind].val;
    push(l,r,ind);
    int mid=(l+r)>>1;
    return query(l,mid,start,end,ind*2)+query(mid+1,r,start,end,ind*2+1);
}
struct rng{
    int l,r;
    ll lnum,rnum;
    rng(int _l,int _r,ll _lnum,ll _rnum){
        l=_l,r=_r,lnum=_lnum,rnum=_rnum;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll d;
    cin>>n>>d;
    seg.resize(4*n+4);
    vec.resize(n+1);
    vector<ll> pre(n+1);
    for(int i=1;i<=n;i++) cin>>vec[i],pre[i]=pre[i-1]+vec[i];
    build(1,n,1);
    vector<vector<pair<int,int>>> events(n+1);
    int q;
    cin>>q;
    vector<ll> ans(q);
    int a,b;
    for(int i=0;i<q;i++){
        cin>>a>>b;
        events[b].push_back(make_pair(a,i));
    }
    vector<rng> st;
    for(int i=1;i<=n;i++){
        int nowl=i,nowr=i;
        ll nowlnum=vec[i],nowrnum=vec[i];
        while(!st.empty()){
            auto [l,r,lnum,rnum]=st.back();
            //cout<<l<<" "<<r<<" "<<lnum<<" "<<rnum<<"\n";
            if(rnum+d<=nowlnum) break;
            st.pop_back();
            ll res=(rnum-nowlnum-1)/d+1;
            if(rnum<=nowlnum) res=0;
            modify(1,n,l,r,-d*res,1);
            nowl=l;
            nowlnum=lnum-d*res;
        }
        st.emplace_back(nowl,nowr,nowlnum,nowrnum);
        for(auto &[l,id]:events[i]){
            if(query(1,n,l,l,1)<0) ans[id]=-1;
            else ans[id]=((pre[i]-pre[l-1])-query(1,n,l,i,1))/d;
        }
    }
    for(auto x:ans) cout<<x<<"\n";
}

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