Submission #1025150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025150		grogu	Fish 3 (JOI24_fish3)	C++14	20 / 100	552 ms	77032 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+10;i++) lazy[i] = llinf;
    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);
    stack<ll> st;
    for(ll i = 1;i<=n;i++){
        while(si(st)&&val[st.top()]>val[i]) st.pop();
        if(si(st)) L[i] = st.top();
        st.push(i);
    }
    for(ll i = 1;i<=n;i++) e[i] = {val[i],i};
    sort(e+1,e+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: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36