Submission #1309867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309867		StefanSebez	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	146 ms	25476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=5e5+50,S=1300;
const ll INF=1e18;
void chmn(ll &x,ll y){x=min(x,y);}
int n,L,q;
int a[N],num[N],prefnum[N];
ll dp1[S+5][S+5][2],dp2[S+5][S+5][2];
ll pref1[N],suf1[N];
ll pref2[N],suf2[N];
int main(){
    scanf("%i%i",&n,&L);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    sort(a+1,a+n+1);
    int m=0;
    for(int i=1;i<=n;){
        int j=i;
        while(j<=n&&a[i]==a[j])j++;
        a[++m]=a[i];
        num[m]=j-i;
        i=j;
    }
    for(int i=m+1;i<=n;i++)a[i]=0;
    for(int i=1;i<=m;i++)prefnum[i]=prefnum[i-1]+num[i];
    if(m<S){
        for(int l=1;l<=m;l++)for(int r=l;r<=m;r++)dp1[l][r][0]=dp1[l][r][1]=INF;
        dp1[1][m][0]=0;
        for(int d=n-1;d>=1;d--){
            for(int l=1;l+d-1<=m;l++){
                int r=l+d-1;
                if(l>1)chmn(dp1[l][r][0],dp1[l-1][r][0]+(ll)abs(a[l-1]-a[l])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(r<m)chmn(dp1[l][r][0],dp1[l][r+1][1]+(ll)abs(a[r+1]-a[l])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(l>1)chmn(dp1[l][r][1],dp1[l-1][r][0]+(ll)abs(a[l-1]-a[r])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(r<m)chmn(dp1[l][r][1],dp1[l][r+1][1]+(ll)abs(a[r+1]-a[r])*(n+1-(prefnum[r]-prefnum[l-1])));
            }
        }
        for(int l=1;l<=m;l++)for(int r=l;r<=m;r++)dp2[l][r][0]=dp2[l][r][1]=INF;
        dp2[1][m][1]=0;
        for(int d=n-1;d>=1;d--){
            for(int l=1;l+d-1<=m;l++){
                int r=l+d-1;
                if(l>1)chmn(dp2[l][r][0],dp2[l-1][r][0]+(ll)abs(a[l-1]-a[l])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(r<m)chmn(dp2[l][r][0],dp2[l][r+1][1]+(ll)abs(a[r+1]-a[l])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(l>1)chmn(dp2[l][r][1],dp2[l-1][r][0]+(ll)abs(a[l-1]-a[r])*(n+1-(prefnum[r]-prefnum[l-1])));
                if(r<m)chmn(dp2[l][r][1],dp2[l][r+1][1]+(ll)abs(a[r+1]-a[r])*(n+1-(prefnum[r]-prefnum[l-1])));
            }
        }
        for(int i=0;i<=m+1;i++)pref1[i]=suf1[i]=INF;
        for(int i=1;i<=m;i++) pref1[i]=min(pref1[i-1],dp1[i][i][0]-(ll)a[i]*(n+1));
        for(int i=m;i>=1;i--) suf1[i]=min(suf1[i+1],dp1[i][i][0]+(ll)a[i]*(n+1));
        for(int i=0;i<=m+1;i++)pref2[i]=suf2[i]=INF;
        for(int i=1;i<=m;i++) pref2[i]=min(pref2[i-1],dp2[i][i][0]-(ll)a[i]*(n+1));
        for(int i=m;i>=1;i--) suf2[i]=min(suf2[i+1],dp2[i][i][0]+(ll)a[i]*(n+1));
    }
    scanf("%i",&q);
    while(q--){
        int u,v,t;scanf("%i%i%i",&u,&v,&t);
        if(m>=S){
            printf("No\n");
            continue;
        }
        ll mn=INF;
        int lb=lower_bound(a+1,a+m+1,v)-a;
        chmn(mn,pref1[lb-1]+(ll)v*(n+1)+abs(u-a[1]));
        chmn(mn,suf1[lb]-(ll)v*(n+1)+abs(u-a[1]));
        chmn(mn,pref2[lb-1]+(ll)v*(n+1)+abs(u-a[m]));
        chmn(mn,suf2[lb]-(ll)v*(n+1)+abs(u-a[m]));
        mn+=n;
        if(mn<=t)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%i%i",&n,&L);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:19:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
Main.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         int u,v,t;scanf("%i%i%i",&u,&v,&t);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~

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