Submission #842204

#	Time	Username	Problem	Language	Result	Execution time	Memory
842204		7mody	Overtaking (IOI23_overtaking)	C++17	65 / 100	3512 ms	25564 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
vector<vector<pair<ll,ll>>> a;
vector<ll> station;
ll all,n,x,m;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    n=N;all=L;x=X;m=M;;
    for(int i=0; i < n;i++){
        if(W[i] > x){
            arr.push_back({W[i],(ll)T[i]});    
        }
    }
    n=arr.size();
    s.resize(m);
    station.resize(m);
    for(int i=0; i < m;i++){
        station[i]=ll(S[i]);
    }
    sort(arr.begin(),arr.end());
    reverse(arr.begin(),arr.end());
    for(int i=0; i < m;i++){
        s[i].resize(n);
    }
    a.resize(m);
    for(int i=0; i < n;i++) s[0][i]=arr[i].second;
    for(int i=1; i < m;i++){
        ll length=S[i]-S[i-1];
        set<pair<ll,ll>> st;
        for(int j=0; j < n;j++){
            ll start=s[i-1][j];
            ll expected=start+(arr[j].first * length);
            ll actual=expected;
            auto it=st.lower_bound({start,0});
            if(it!=st.begin()){
                it--;
                pair<ll,ll> curr=*it;
                if(start > curr.first && curr.second > actual) actual=curr.second;
            }
            s[i][j]=actual;
            st.insert({start,actual});
        }
        vector<pair<ll,ll>> curr(n);
        for(int j=0; j < n;j++){
            curr[j]={s[i-1][j],s[i][j]};
        }
        sort(curr.begin(),curr.end());
        a[i]=curr;
    }
    // for(auto c : a){
    //     for(auto g : c) cout << g.first << ' ' << g.second << "   ";
    //     cout << endl;
    // }
}

long long arrival_time(long long Y)
{
    ll ans=Y;
    for(int i=1; i < m;i++){
        ll length = station[i]-station[i-1];
        ll start = ans;
        ll expected = start + (x*length);
        ll actual=expected;
        int l=0,r=n-1;
        int id=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[i][mid].first < start) id=mid,l=mid+1;
            else r=mid-1;
        }
        if(id!=-1){
            pair<ll,ll> curr=a[i][id];
            // cout << curr.first << ' ' << curr.second << ' ' << start << ' ' << actual << endl;
            if(start > curr.first && curr.second > actual) actual=curr.second;
        }
        ans=actual;
    }
    return ans;
}

// void solve(){
//     int l,q; cin >> l >> n >> x >> m >> q;
//     vector<ll> T(n);
//     vector<int> W(n);
//     for(int i=0; i < n;i++) cin >> T[i];
//     for(int i=0; i < n;i++) cin >> W[i];
//     vector<int> S(m);
//     for(int i=0; i < m;i++) cin >> S[i];
//     init(l,n,T,W,x,m,S);
//     while(q--){
//         ll temp; cin >> temp;
//         cout << arrival_time(temp) << endl;
//     }
// }

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     int t=1;
//     // cin >> t;
//     while(t--) solve();
//     return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35