Submission #1316588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316588		user736482	Fish 3 (JOI24_fish3)	C++20	100 / 100	511 ms	52624 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
    return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
    return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
template<ll MOD=998244353>
struct mint_t{
    ll x;
    mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
    mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
    mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
    mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
    mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
    mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
    mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
    mint_t fp(ll y)const{
        mint_t a=1,b=x;
        while(y){
            if(y&1)a*=b;
            b*=b;
            y/=2;
        }
        return a;
    }
    mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
    mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
    ll x;
    in>>x;
    a=mint_t<MOD>(x);
    return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
    out<<a.x;
    return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
    if(b>a || a<0)return 0;
    return fct[a]/fct[b]/fct[a-b];
}
ll ans[300007];
ll sg[POT],mn[POT],sg2[POT],lz[POT];
void pusz2(ll v,ll l,ll r,ll x){
    if(x!=-INFL){
        lz[v]=x;
        sg2[v]=x*(r-l+1)-sg[v];
        if(mn[v]<x)sg2[v]=-INFL;
    }
}
void pusz(ll v,ll l,ll r){
    pusz2(v*2,l,(l+r)/2,lz[v]);pusz2(v*2+1,(l+r)/2+1,r,lz[v]);lz[v]=-INFL;
}
void st(ll v,ll l,ll r,ll pocz,ll kon,ll x){
    if(l>kon || r<pocz)return;
    if(l>=pocz && r<=kon){
        pusz2(v,l,r,x);
    }
    else{
        pusz(v,l,r);
        st(v*2,l,(l+r)/2,pocz,kon,x);st(v*2+1,(l+r)/2+1,r,pocz,kon,x);
        sg2[v]=max(-INFL,sg2[v*2]+sg2[v*2+1]);
    }
}
ll sm(ll v,ll l,ll r,ll pocz,ll kon){
    if(l>kon || r<pocz)return 0;
    if(l>=pocz && r<=kon)return sg2[v];
    pusz(v,l,r);
    return max(-INFL,sm(v*2,l,(l+r)/2,pocz,kon)+sm(v*2+1,(l+r)/2+1,r,pocz,kon));
}
vii o[300007];
void solve(){
    ll n,q,a,b,d,c=0;
    vi v,v2;
    cin>>n>>d;
    for(ll i=0;i<n;i++){
        cin>>a;
        if(i && v.back()%d>a%d)c++;
        v.pb(a);
        v2.pb(-(a/d-c));
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        o[b-1].pb({a,i});
    }
    for(ll i=0;i<n;i++){
        sg[POT/2+i]=v2[i];
        mn[POT/2+i]=v2[i]+v[i]/d;
    }
    for(ll i=POT/2-1;i;i--){
        sg[i]=sg[i*2]+sg[i*2+1];
        mn[i]=min(mn[i*2],mn[i*2+1]);
    }
    //cout<<v2;
    stack<pip>s;
    s.push({INFL,{0,0}});
    for(ll i=0;i<n;i++){
        pii ns={i+1,i+1};
        while(s.top().ff<v2[i]){
            ns.ff=s.top().ss.ff;s.pop();
        }
        //cout<<i<<" "<<ns<<"\n";
        s.push({v2[i],ns});
        st(1,1,POT/2,ns.ff,ns.ss,v2[i]);
        for(pii j : o[i]){
            //cout<<i+1<<" "<<j.ff<<" "<<j.ss<<"\n";
            ans[j.ss]=sm(1,1,POT/2,j.ff,i+1);
        }
    }
    for(ll i=0;i<q;i++)cout<<max(-1LL,ans[i])<<"\n";
}
int main(){
    fct[0]=1;
    for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}

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