제출 #1061814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061814		Warinchai	Fish 3 (JOI24_fish3)	C++14	100 / 100	374 ms	69996 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[3000005];
int n,d;
struct tag{
    int del;
    tag(int _del=0){
        del=_del;
    }
    void apply(tag x){
        //cerr<<x.del<<" "<<del<<"\n";
        del+=x.del;
    }
};
struct node{
    int val;
    int left;
    node(int _val=0,int _left=LLONG_MAX){
        val=_val;
        left=_left;
    }
    void apply(int st,int en,tag x){
        val-=(en-st+1)*x.del;
        left-=x.del;
        if(left<0)val=-1;
    }
    friend node operator+(node a,node b){
        node c;
        c.val=a.val+b.val;
        c.left=min(a.left,b.left);
        if(a.val<0||b.val<0)c.val=-1;
        return c;
    }
};
struct segtree{
    node info[1200005];
    tag lz[1200005];
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=node(ar[st],ar[st]));
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
    void apply(int st,int en,int i,tag x){
        info[i].apply(st,en,x);
        //cerr<<"apply:"<<i<<"\n";
        lz[i].apply(x);
    }
    void push(int st,int en,int i){
        int m=(st+en)/2;
        apply(st,m,i*2,lz[i]);
        apply(m+1,en,i*2+1,lz[i]);
        lz[i].del=0;
    }
    void upd(int st,int en,int i,int l,int r,tag x){
        if(st>r||en<l)return;
        if(st>=l&&en<=r){
            apply(st,en,i,x);
            //cerr<<"info:"<<st<<" "<<en<<" "<<info[i].val<<"\n";
            return;
        }
        int m=(st+en)/2;
        push(st,en,i);
        upd(st,m,i*2,l,r,x);
        upd(m+1,en,i*2+1,l,r,x);
        info[i]=info[i*2]+info[i*2+1];
        //cerr<<"info:"<<st<<" "<<en<<" "<<info[i].val<<"\n";
    }
    node fans(int st,int en,int i,int l,int r){
        if(st>=l&&en<=r)return info[i];
        if(st>r||en<l)return node();
        int m=(st+en)/2;
        push(st,en,i);
        return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
    }
    void print(int st,int en,int i){
        //cerr<<st<<" "<<en<<" "<<info[i].val<<"\n";
        if(st==en)return;
        int m=(st+en)/2;
        print(st,m,i*2);
        print(m+1,en,i*2+1);
    }
}tr;
struct block{
    int l,r,rval,lval;
    block(int id=0,int _val=0){
        l=r=id;
        rval=lval=_val;
    }
    friend block operator+(block a,block b){
        block c;
        c.l=a.l;
        c.r=b.r;
        c.rval=b.rval;
        c.lval=a.lval;
        return c;
    }
};
vector<pair<int,int>>qr[300005];
int sum[300005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>ar[i],sum[i]=sum[i-1]+ar[i];
    tr.build(1,n,1);
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int l,r;cin>>l>>r;
        qr[r].push_back({l,i});
    }
    stack<block>s;
    vector<int>ans(q,0);
    //cerr<<"work\n";
    for(int i=1;i<=n;i++){
        //cerr<<"work\n";
        block cur(i,ar[i]);
        while(!s.empty()&&cur.lval<=s.top().rval){
            int del=s.top().rval-cur.lval;
            int dec=del/d;
            if(del%d!=0)dec++;
            s.top().rval-=dec*d;
            s.top().lval-=dec*d;
            tr.upd(1,n,1,s.top().l,s.top().r,tag(dec*d));
            cur=s.top()+cur;
            s.pop();
        }
        s.push(cur);
        //cerr<<"i:"<<i<<"-"<<cur.l<<" "<<cur.r<<" "<<cur.lval<<" "<<cur.rval<<" "<<tr.fans(1,n,1,1,i).val<<"\n";
        //tr.print(1,n,1);
        for(auto x:qr[i]){
            int v=tr.fans(1,n,1,x.first,i).val;
            ans[x.second]=(v==-1?-1:(sum[i]-sum[x.first-1]-v)/d);
        }
    }
    //for(int i=1;i<=n;i++)cerr<<tr.fans(1,n,1,i,i).val<<" ";
    //cerr<<"\n";
    //cerr<<tr.fans(1,n,1,1,n).val<<"\n";
    for(auto x:ans)cout<<x<<"\n";
    //tr.print(1,n,1);
}

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