Submission #1025128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025128		grogu	Fish 3 (JOI24_fish3)	C++14	55 / 100	600 ms	87028 KiB

Main

    #define here cerr<<"===========================================\n"
    #define dbg(x) cerr<<#x<<": "<<x<<endl;
    #include <bits/stdc++.h>
    #define ld double
    #define ll long long
    #define ull unsigned long long
    #define llinf 100000000000000000LL // 10^17
    #define iinf 2000000000 // 2*10^9
    #define pb push_back
    #define eb emplace_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
    #define si(a) (ll)(a.size())
    using namespace std;
     
    #define maxn 300005
    ll n,q,d;
    ll a[maxn];
    ll pa[maxn];
    ll b[maxn];
    ll c[maxn];
    ll pb[maxn];
    ll ps[maxn];
    pll Q[maxn];
    ll fl[maxn];
    ll t[2*maxn],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
    pll e[maxn];
    vector<pll> ask[maxn];
    ll ans[maxn];
    ll L[maxn];
    ll val[maxn];
    ll pv[maxn];
    void init(ll &v,ll tl,ll tr){
        if(!v) v = ++tsz;
        if(tl==tr){t[v] = fl[tl];return;}
        ll mid = (tl+tr)/2;
        init(ls[v],tl,mid);
        init(rs[v],mid+1,tr);
        t[v] = max(t[ls[v]],t[rs[v]]);
    }
    ll get(ll v,ll tl,ll tr,ll l,ll r){
        if(l>r||l>tr||tl>tr||tl>r) return 0;
        if(tl>=l&&tr<=r) return t[v];
        ll mid = (tl+tr)/2;
        return max(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
    }
    ll t2[2*maxn];
    ll lazy[2*maxn];
    void init2(ll v,ll tl,ll tr){
        if(tl==tr){t2[v] = val[tl];return;}
        ll mid = (tl+tr)/2;
        init2(ls[v],tl,mid);
        init2(rs[v],mid+1,tr);
        t2[v] = t2[ls[v]] + t2[rs[v]];
    }
    void push(ll v,ll tl,ll tr){
        ll mid = (tl+tr)/2;
        if(lazy[v]==llinf) return;
        t2[ls[v]]=lazy[v]*(mid-tl+1);
        t2[rs[v]]=lazy[v]*(tr-(mid+1)+1);
        lazy[ls[v]]=lazy[v];
        lazy[rs[v]]=lazy[v];
        lazy[v] = llinf;
    }
    ll sum(ll v,ll tl,ll tr,ll l,ll r){
        push(v,tl,tr);
        if(l>r||l>tr||tl>r||tl>tr) return 0;
        if(tl>=l&&tr<=r) return t2[v];
        ll mid = (tl+tr)/2;
        return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
    }
    void upd2(ll v,ll tl,ll tr,ll l,ll r,ll x){
        push(v,tl,tr);
        if(l>r||l>tr||tl>r||tl>tr) return;
        if(tl>=l&&tr<=r){
            t2[v]=(tr-tl+1)*x;
            lazy[v]=x;
            return;
        }
        ll mid = (tl+tr)/2;
        upd2(ls[v],tl,mid,l,r,x);
        upd2(rs[v],mid+1,tr,l,r,x);
        t2[v] = t2[ls[v]] + t2[rs[v]];
    }
    void tc(){
        cin >> n >> d;
        for(ll i = 1;i<=n;i++) cin >> a[i];
        for(ll i = 0;i<=2*n;i++) lazy[i] = llinf;
        stack<ll> st;
        for(ll i = 1;i<=n;i++){
            while(si(st)&&a[st.top()]>a[i]) st.pop();
            if(si(st)) L[i] = st.top();
            st.push(i);
        }
        for(ll i = 1;i<=n;i++) e[i] = {a[i],i};
        for(ll i = 1;i<=n;i++) c[i] = a[i]%d;
        for(ll i = 1;i<=n;i++) pa[i] = pa[i-1] + a[i];
        cin >> q;
        for(ll i = 1;i<=q;i++){
            cin >> Q[i].fi >> Q[i].sc;
            ask[Q[i].sc].pb({Q[i].fi,i});
        }
        for(ll i = 2;i<=n;i++){
            b[i] = c[i]-c[i-1];
            if(b[i]<0) b[i]+=d;
            ps[i] = ps[i-1] + b[i];
        }
        for(ll i = 1;i<=n;i++) pb[i] = pb[i-1] + b[i]*i;
        for(ll i = 1;i<=n;i++){
            ll tl = 1,tr = i,mid,rez = i;
            while(tl<=tr){
                mid = (tl+tr)/2;
                if(ps[i]-ps[mid]+c[mid]<=a[i]) rez = mid,tr = mid-1;
                else tl = mid+1;
            }
            fl[i] = rez;
        }
        init(root,1,n);
        for(ll i = 1;i<=n;i++) val[i] = a[i] - ps[i];
        for(ll i = 1;i<=n;i++) pv[i] = pv[i-1] + val[i];
        init2(root,1,n);
        //ceri(L,1,n);
        for(ll j = 1;j<=n;j++){
            ll r = e[j].sc;
            upd2(root,1,n,L[r]+1,r,val[r]);
            for(pll p : ask[r]){
                ll l = p.fi;
                ll gr = get(root,1,n,l,r);
                if(gr>l){
                    ans[p.sc] = -1;
                    continue;
                }
                ll uk = 0;
     
                //uk+=pa[r]-pa[l-1];
                //uk+=(ps[r]-ps[l]+c[l]);
                uk+=(pv[r-1]-pv[l-1]) - sum(root,1,n,l,r-1);
                //cerr<<"LR: "<<l<< " "<<r<< " "<<sum(root,1,n,l,r)<<endl;
                ans[p.sc] = uk/d;
            }
        }
        for(ll i = 1;i<=q;i++) cout<<ans[i]<<endl;
    }
    /**
    6 3
    16 14 13 8 6 5
    4
    1 4
    2 5
    3 3
    1 6
     
    5 1
    3 1 4 1 5
    3
    1 5
    2 4
    3 5
    **/
    int main(){
    	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    	int t; t = 1;
    	while(t--){
    		tc();
    	}
    	return (0-0);
    }

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