Submission #1150167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150167		Cookie197	Marathon Race 2 (JOI24_ho_t3)	C++20	81 / 100	179 ms	127728 KiB

Main

// Cookie197 
// i am absolute trash
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include <cassert>
#include<random>
using namespace std;
#define i_am_trashQ_Q ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define mod 998244353
//#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

ll n,l,q,m;
ll x[500005];
ll pos[500005], balls[500005], pre[500005], suf[500005];

ll dpa[2005][2005][2], dpb[2005][2005][2];
ll apre[2005], asuf[2005], bpre[2005], bsuf[2005];


void solve(){
    ll s,g,t; cin>>s>>g>>t;

    int left = 0, right = m+1;
    while(left < right){
        int mid = (left + right) >> 1;
        if (pos[mid] > g) right = mid;
        else left = mid+1;
    }
    
    ll ans = inf;
    /*for (int i=0;i<=m;i++){
        ans = min(ans, dpa[i][m-i][0] + abs(pos[i] - g) * (n+1) + abs(s - pos[1]));
        ans = min(ans, dpb[i][m-i][0] + abs(pos[i] - g) * (n+1) + abs(s - pos[m]));
    }*/
    if (left > 0) ans = min(ans, apre[left-1] + g*(n+1) + abs(s-pos[1]));
    if (left > 0) ans = min(ans, bpre[left-1] + g*(n+1) + abs(s-pos[m]));
    if (left <= m)ans = min(ans, asuf[left] - g*(n+1) + abs(s-pos[1]));
    if (left <= m)ans = min(ans, bsuf[left] - g*(n+1) + abs(s-pos[m]));
    //out(ans);
    if (ans + n <= t) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

signed main(){
    i_am_trashQ_Q
    cin>>n>>l;
    if (n > 2000) return 0;
    for (int i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+1+n);
    int last = -1;
    for (int i=1;i<=n;i++){
        if (x[i] != last){
            m++;
            pos[m] = x[i];
            balls[m] = 1;
            last = x[i];
        }else balls[m]++;
    }
    for (int i=1;i<=m;i++) pre[i] = pre[i-1] + balls[i];
    for (int i=1;i<=m;i++) suf[i] = suf[i-1] + balls[m-i+1];


    // 
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) dpa[i][j][0] = dpa[i][j][1] = dpb[i][j][0] = dpb[i][j][1] = inf;
    dpa[1][0][0] = 0;
    dpa[1][0][1] = inf;
    dpa[0][1][1] = inf;
    dpa[0][1][0] = inf;
    dpb[1][0][0] = inf;
    dpb[1][0][1] = inf;
    dpb[0][1][1] = 0;
    dpb[0][1][0] = inf;
    
    for (int i=2;i<=m;i++){
        dpa[i][0][0] = dpa[i-1][0][0] + (pre[i-1] + 1) * (pos[i] - pos[i-1]);
        dpb[i][0][0] = dpb[i-1][0][0] + (pre[i-1] + 1) * (pos[i] - pos[i-1]);
    }
    for (int j=2;j<=m;j++){
        dpa[0][j][1] =  dpa[0][j-1][1] + (suf[j-1] + 1) * (pos[m-j+2] - pos[m-j+1]);
        dpb[0][j][1] =  dpb[0][j-1][1] + (suf[j-1] + 1) * (pos[m-j+2] - pos[m-j+1]);
    }
    for (int i=1;i<=m;i++){
        for (int j=1;i+j<=m;j++){
            ll r = inf;
            r = min(r, dpa[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dpa[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dpa[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dpa[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            dpa[i][j][0] = r;

            r = inf;
            r = min(r, dpa[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            r = min(r, dpa[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dpa[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1));
            r = min(r, dpa[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1));
            dpa[i][j][1] = r;

            r = inf;
            r = min(r, dpb[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dpb[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dpb[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dpb[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            dpb[i][j][0] = r;

            r = inf;
            r = min(r, dpb[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            r = min(r, dpb[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dpb[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1));
            r = min(r, dpb[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1));
            dpb[i][j][1] = r;
        }
    }
    apre[0] = dpa[0][m][0] - pos[0]*(n+1);
    bpre[0] = dpb[0][m][0] - pos[0]*(n+1);
    for (int i=1;i<=m;i++){
        apre[i] = min(apre[i-1], dpa[i][m-i][0] - pos[i]*(n+1));
        bpre[i] = min(bpre[i-1], dpb[i][m-i][0] - pos[i]*(n+1));
    }
    asuf[m] = dpa[m][0][0] + pos[m]*(n+1);
    bsuf[m] = dpb[m][0][0] + pos[m]*(n+1);
    for (int i=m-1;i>=0;i--){
        asuf[i] = min(asuf[i+1], dpa[i][m-i][0] + pos[i]*(n+1));
        bsuf[i] = min(bsuf[i+1], dpb[i][m-i][0] + pos[i]*(n+1));
    }
    
    cin>>q;
    while(q--){
        solve();
    }
}

• 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: 0 / 19