Submission #1148615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148615		koukirocks	Marathon Race 2 (JOI24_ho_t3)	C++20	52 / 100	3 ms	4420 KiB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

ll dp[900][900][2];

void cal(int n,int q,vector<pii> &bll,vector<pair<pii,int>> &Q,vector<bool> &ans) {
    vector<int> pre(n+2);
    for (int i=1;i<=n+1;i++) {
        pre[i]=pre[i-1]+bll[i].S;
    }
    dp[0][n+1][0]=0;
    dp[0][n+1][1]=bll[n].F-bll[1].F;
    for (int i=1;i<=n;i++) {
        dp[i][n+1][0]=dp[i-1][n+1][0]+(bll[i].F-bll[i-1].F)*(pre[i-1]+1)+bll[i].S;
        // cout<<i<<" "<<n+1<<" 0 "<<dp[i][n+1][0]<<" i n+1 0 dp\n";
    }
    for (int j=n;j>=1;j--) {
        // cout<<j<<"\n"<<flush;
        dp[0][j][1]=dp[0][j+1][1]+(bll[j+1].F-bll[j].F)*(pre[n]-pre[j]+1)+bll[j].S;
        // cout<<0<<" "<<j<<" 1 "<<dp[0][j][1]<<" 0 j 1 dp\n";
    }
    auto get = [&](int i,int j,int k,pii nxt) {
        if (i==0 and k==0) return INF;
        if (j==n+1 and k==1) return INF;
        // cout<<i<<" "<<j<<" "<<k<<" ijk\n";
        if (k==0) return dp[i][j][k]+abs((nxt.F-bll[i].F)*(pre[i]+pre[n]-pre[j-1]+1))+nxt.S;
        else return dp[i][j][k]+abs((nxt.F-bll[j].F)*(pre[i]+pre[n]-pre[j-1]+1))+nxt.S;
    };
    for (int i=1;i<=n;i++) {
        for (int j=n;j>i;j--) {
            dp[i][j][0]=min(get(i-1,j,0,bll[i]),get(i-1,j,1,bll[i]));
            dp[i][j][1]=min(get(i,j+1,0,bll[j]),get(i,j+1,1,bll[j]));
            // cout<<get(i-1,j,0,bll[i])<<" "<<get(i-1,j,1,bll[i])<<" cho\n";
            // cout<<i<<" "<<j<<" 0 "<<dp[i][j][0]<<" ij dp\n";
            // cout<<get(i,j+1,0,bll[j])<<" "<<get(i,j+1,1,bll[j])<<" cho\n";
            // cout<<i<<" "<<j<<" 1 "<<dp[i][j][1]<<" ij dp\n";
        }
    }
    for (int i=1;i<=q;i++) {
        auto pos=lower_bound(all(bll),pii(Q[i].F.S,0))-bll.begin();
        // cout<<pos<<" pos\n";
        int tm;
        if (pos==0) tm=dp[0][1][1]+abs(Q[i].F.S-bll[1].F)*(pre[n]+1);
        else if (pos==n+2) tm=dp[n][n+1][0]+abs(Q[i].F.S-bll[n].F)*(pre[n]+1);
        else tm=min(dp[pos-1][pos][0]+abs(Q[i].F.S-bll[pos-1].F)*(pre[n]+1),dp[pos-1][pos][1]+abs(Q[i].F.S-bll[pos].F)*(pre[n]+1));
        tm+=abs(Q[i].F.F-bll[1].F);
        // cout<<tm<<" ";
        ans[i]=(tm<=Q[i].S);
    }
    // cout<<" tm\n";
}

int main() {
    speed;
    int n,l;
    cin>>n>>l;
    vector<int> cnt(l+1);
    vector<pii> bll;
    for (int i=1;i<=n;i++) {
        int x;
        cin>>x;
        cnt[x]++;
    }
    bll.push_back({0,0});
    for (int i=0;i<=l;i++) {
        if (cnt[i]) bll.emplace_back(i,cnt[i]);
    }
    bll[0]={bll[1].F,0};
    n=bll.size()-1;
    bll.push_back({bll.back().F,0});
    // for (auto [a,b]:bll) {
    //     cout<<a<<" "<<b<<" bll\n";
    // }
    if (n>=900) {
        int q;
        cin>>q;
        while (q--) {
            int s,e,t;
            cin>>s>>e>>t;
            cout<<"No\n";
        }
        return 0;
    }
    int q;
    cin>>q;
    vector<pair<pii,int>> qry(q+1);
    for (int i=1;i<=q;i++) {
        int t,l,r;
        cin>>l>>r>>t;
        qry[i]={{l,r},t};
    }
    vector<bool> ansl(q+1);
    // cout<<n<<"\n"<<flush;
    cal(n,q,bll,qry,ansl);
    for (int i=0;i<=n+1;i++) {
        bll[i]={l-bll[i].F,bll[i].S};
    }
    reverse(all(bll));
    for (int i=1;i<=q;i++) {
        qry[i].F.F=l-qry[i].F.F;
        qry[i].F.S=l-qry[i].F.S;
    }
    // for (auto [a,b]:bll) {
    //     cout<<a<<" "<<b<<" bll\n";
    // }
    vector<bool> ansr(q+1);
    cal(n,q,bll,qry,ansr);
    for (int i=1;i<=q;i++) {
        if (ansl[i] or ansr[i]) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

/*
6 100
0 50 100 0 50 100
1
70 20 600
*/

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