Submission #1326529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326529		goodpjw2008	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	11 ms	17516 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int balls[500002],bs[500002],rbs[500002],dp[500002],rdp[500002],tol[500002],tor[500002];
const int MAX=1e15;
int range(int l, int r){
    return dp[r]-dp[l-1]-bs[l-1]*(r-l+1);
}
int rrange(int l, int r){
    return rdp[l]-rdp[r+1]-rbs[r+1]*(r-l+1);
}
int triple(int s, int a, int b, int c, int e){
    if(c==-1){
        return range(s,a-1)
        +(e-a)*(bs[a-1]-bs[s-1]+1)
        +rrange(b+1,e)+(e-b)*(bs[a-1]-bs[s-1])
        +(b-a)*(bs[a-1]-bs[s-1]+1+rbs[b+1]-rbs[e+1])
        +range(a,b)+(b-a+1)*(rbs[b+1]-rbs[e+1]+bs[a-1]-bs[s-1]);
    }
    else{
        return rrange(c+1,e)
        +(c-s)*(rbs[c+1]-rbs[e+1]+1)
        +range(s,b-1)+(b-s)*(rbs[c+1]-rbs[e+1])
        +(c-b)*(rbs[c+1]-rbs[e+1]+1+bs[b-1]-bs[s-1])
        +rrange(b,c)+(c-b+1)*(bs[b-1]-bs[s-1]+rbs[c+1]-rbs[e+1]);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,l,x,q,y,z,lp=1231231,rp=0;
    cin>>n>>l;
    for(int i = 1; i <= n; i++){
        cin>>x;
        x++;
        balls[x]++;
        lp=min(lp,x);
        rp=max(rp,x);
    }
    for(int i = 1; i <= l+1; i++){
        bs[i]=bs[i-1]+balls[i];
        dp[i]=dp[i-1]+bs[i]+1;
    }
    for(int i = l+1; i >= 1; i--){
        rbs[i]=rbs[i+1]+balls[i];
        rdp[i]=rdp[i+1]+rbs[i]+1;
    }
    int p=lp;
    for(int i = lp; i <= rp; i++){
        while(p<i&&triple(lp,p,i,-1,rp)>=triple(lp,p+1,i,-1,rp))p++;
        tol[i]=triple(lp,p,i,-1,rp);
    }
    p=rp;
    for(int i = rp; i >= lp; i--){
        while(p>i&&triple(lp,-1,i,p,rp)>=triple(lp,-1,i,p-1,rp))p--;
        tor[i]=triple(lp,-1,i,p,rp);
    }
    cin>>q;
    while(q--){
        cin>>x>>y>>z;
        x++;
        y++;
        int l,r;
        //l
        if(x<y){
            if(x<lp){
                if(y<lp){
                    l=abs(rp-x)-1+rdp[y]-rdp[rp+1];
                }
                else if(y<rp){
                    l=dp[y-1]-dp[x]+balls[x]+abs(rp-y)*(bs[y-1]-bs[x]+1+balls[x])+rdp[y]-rdp[rp+1]+(rp-y+1)*(bs[y-1]-bs[x]+balls[x]);
                }
                else{
                    l=dp[y]-dp[x]+balls[x];
                }
            }
            else if(x<rp){
                if(y<lp){
                    l=MAX;
                }
                else if(y<rp){
                    l=abs(x-lp)-1+dp[y-1]-dp[lp-1]+abs(rp-y)*(bs[y-1]-bs[lp-1]+1)+rdp[y]-rdp[rp+1]+(rp-y+1)*(bs[y-1]-bs[lp-1]);
                }
                else{
                    l=abs(x-lp)-1+dp[y]-dp[lp-1];
                }
            }
            else{
                if(y<lp){
                    l=MAX;
                }
                else if(y<rp){
                    l=MAX;
                }
                else{
                    l=abs(x-lp)-1+dp[y]-dp[lp-1];
                }
            }
        }
        else{
            if(x<lp){
                if(y<lp){
                    l=abs(rp-x)-1+rdp[y]-rdp[rp+1];
                }
                else if(y<rp){
                    l=MAX;
                }
                else{
                    l=MAX;
                }
            }
            else if(x<rp){
                if(y<lp){
                    l=abs(x-lp)-1+abs(rp-lp)+rdp[y]-rdp[rp+1];
                }
                else if(y<rp){
                    l=abs(x-lp)-1+dp[y-1]-dp[lp-1]+abs(rp-y)*(bs[y-1]-bs[lp-1]+1)+rdp[y]-rdp[rp+1]+(rp-y+1)*(bs[y-1]-bs[lp-1]);
                }
                else{
                    l=MAX;
                }
            }
            else{
                if(y<lp){
                    l=abs(x-lp)-1+abs(rp-lp)+rdp[y]-rdp[rp+1];
                }
                else if(y<rp){
                    l=abs(x-lp)-1+dp[y-1]-dp[lp-1]+abs(rp-y)*(bs[y-1]-bs[lp-1]+1)+rdp[y]-rdp[rp+1]+(rp-y+1)*(bs[y-1]-bs[lp-1]);
                }
                else{
                    l=abs(x-lp)-1+dp[y]-dp[lp-1];
                }
            }
            //r
        }
        if(x<y){
            if(x<lp){
                if(y<lp){
                    r=abs(rp-x)-1+rdp[y]-rdp[rp+1];//ok
                }
                else if(y<rp){
                    r=abs(rp-x)-1+rdp[y+1]-rdp[rp+1]+(y-lp)*(rbs[y+1]-rbs[rp+1]+1)+dp[y]-dp[lp-1]+(y-lp+1)*(rbs[y+1]-rbs[rp+1]);//ok
                }
                else{
                    r=abs(rp-x)-1+abs(rp-lp)+dp[y]-dp[lp-1];//ok
                }
            }
            else if(x<rp){
                if(y<lp){
                    r=MAX;//ok
                }
                else if(y<rp){
                    r=abs(rp-x)-1+rdp[y+1]-rdp[rp+1]+(y-lp)*(rbs[y+1]-rbs[rp+1]+1)+dp[y]-dp[lp-1]+(y-lp+1)*(rbs[y+1]-rbs[rp+1]);//ok
                }
                else{
                    r=abs(rp-x)-1+abs(rp-lp)+dp[y]-dp[lp-1];//ok
                }
            }
            else{
                if(y<lp){
                    r=MAX;//ok
                }
                else if(y<rp){
                    r=MAX;//ok
                }
                else{
                    r=abs(x-lp)-1+dp[y]-dp[lp-1];//ok
                }
            }
        }
        else{
            if(x<lp){
                if(y<lp){
                    r=abs(rp-x)-1+rdp[y]-rdp[rp+1];//ok
                }
                else if(y<rp){
                    r=MAX;//ok
                }
                else{
                    r=MAX;//ok
                }
            }
            else if(x<rp){
                if(y<lp){
                    r=abs(rp-x)-1+rdp[y]-rdp[rp+1];//ok
                }
                else if(y<rp){
                    r=abs(rp-x)-1+rdp[y+1]-rdp[rp+1]+(y-lp)*(rbs[y+1]-rbs[rp+1]+1)+dp[y]-dp[lp-1]+(y-lp+1)*(rbs[y+1]-rbs[rp+1]);//ok
                }
                else{
                    r=MAX;//ok
                }
            }
            else{
                if(y<lp){
                    r=rdp[y]-rdp[x]+balls[x];//ok
                }
                else if(y<rp){
                    r=rdp[y+1]-rdp[x]+balls[x]+(y-lp)*(rbs[y+1]-rbs[x]+1+balls[x])+dp[y]-dp[lp-1]+(y-lp+1)*(rbs[y+1]-rbs[x]+balls[x]);//ok
                }
                else{
                    r=abs(x-lp)-1+dp[y]-dp[lp-1];//ok
                }
            }
        }
        //cerr<<l<<' '<<r<<'\n';
        if(lp<=y&&y<=rp){
            l=min(l,tol[y]+abs(x-lp)-1);
            r=min(r,tor[y]+abs(rp-x)-1);
        }
        //cerr<<l<<' '<<r<<'\n';
        if(min(l,r)>z)cout<<"No\n";
        else cout<<"Yes\n";
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19