Submission #1015506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015506		ReLice	Marathon Race 2 (JOI24_ho_t3)	C++17	100 / 100	300 ms	144720 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=1e9+7;
const ll N=2e3+7;
const ll M=5e5;
const ld eps=1e-9;
ll c[M];
ll pref[N];
vll v;
ll n,q,L;
ll dp[2][N][N][2];
ll sum(ll l,ll r){
    return pref[l]+pref[n]-pref[r-1]+1;
}
void solve(){
    ll i,j;
    cin>>n>>L;
    set<ll> st;
    for(i=0;i<n;i++){
        ll a;
        cin>>a;
        st.ins(a);
        c[a]++;
    }
    n=st.sz;
    v.pb(-1);
    for(auto i : st){
        v.pb(i);
    }
    for(i=1;i<=n;i++) pref[i]=pref[i-1]+c[v[i]];
    if(n>2000){
        cin>>q;
        for(i=0;i<q;i++){
            ll s,g,t;
            cin>>s>>g>>t;
            cout<<"No"<<endl;
        }
        return;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][1][n][0]=0;
    dp[1][1][n][1]=0;
    for(ll len=n-1;len>0;len--){
        for(ll l=1;l<=n-len;l++){
            ll r=l+len;
            for(i=0;i<2;i++){
                chmin(dp[i][l][r-1][0],dp[i][l][r][1]+sum(l-1,r)*(v[r]-v[l]));
                chmin(dp[i][l][r-1][1],dp[i][l][r][1]+sum(l-1,r)*(v[r]-v[r-1]));
                chmin(dp[i][l+1][r][0],dp[i][l][r][0]+sum(l,r+1)*(v[l+1]-v[l]));
                chmin(dp[i][l+1][r][1],dp[i][l][r][0]+sum(l,r+1)*(v[r]-v[l]));
            }
        }
    }/*
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            cout<<i<<' '<<j<<endl;
            cout<<dp[0][i][j][0]<<' '<<dp[0][i][j][1]<<endl;
            cout<<dp[1][i][j][0]<<' '<<dp[1][i][j][1]<<endl<<endl;
        }
    }*/
    for(i=1;i<=n;i++){
        for(j=0;j<2;j++){
            chmin(dp[j][i][i][0],dp[j][i][i][1]);
        }
    }
    cin>>q;
    for(i=0;i<q;i++){
        ll s,g,t;
        cin>>s>>g>>t;
        if(n==1){
            if(t>=abs(s-v[1])+abs(g-v[1])*(c[v[1]]+1)+pref[n])cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
            continue;
        }
        ll g2=lb(all(v),g)-v.begin();
        if(g2==1)g2++;
        if(g2==v.sz)g2--;
        //cout<<g2<<endl;
        //cout<<abs(s-v.bc)+dp[1][g2-1][g2-1][0]+abs(v[g2-1]-g)*(pref[n]+1)+pref[n]<<endl;
        if(t>=abs(s-v[1])+dp[0][g2][g2][0]+abs(v[g2]-g)*(pref[n]+1)+pref[n] ||
           t>=abs(s-v[1])+dp[0][g2-1][g2-1][0]+abs(v[g2-1]-g)*(pref[n]+1)+pref[n] ||
           t>=abs(s-v.bc)+dp[1][g2][g2][0]+abs(v[g2]-g)*(pref[n]+1)+pref[n] ||
           t>=abs(s-v.bc)+dp[1][g2-1][g2-1][0]+abs(v[g2-1]-g)*(pref[n]+1)+pref[n]){
            cout<<"Yes"<<endl;
        }else cout<<"No"<<endl;
    }

}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
3 100
3 3 3
2
3 3 2
3 3 3



*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:116:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         if(g2==v.sz)g2--;
      |              ^

• 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