Submission #844733

#	Time	Username	Problem	Language	Result	Execution time	Memory
844733		7mody	Overtaking (IOI23_overtaking)	C++17	9 / 100	1 ms	604 KiB

overtaking

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

struct item{
    ll first,second,res;
};

vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
vector<vector<item>> a;
vector<vector<item>> dp;
vector<ll> station;
vector<vector<item>> temp;
ll n,x,m,mx;

bool p(item a,item b){
    if(a.first==b.first) return a.second > b.second;
    return a.first < b.first;
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    n=N;x=X;m=M;
    mx=L;
    dp.resize(m);
    for(int i=0; i < n;i++){
        if(W[i] > x){
            arr.push_back({W[i],(ll)T[i]});    
        }
    }
    temp.resize(m);
    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()); // i love alwawi he is very smart. from SAAD
    reverse(arr.begin(),arr.end());
    for(int i=0; i < m;i++){
        s[i].resize(n);
        temp[i].resize(n);
        dp[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<item> curr(n);
        for(int j=0; j < n;j++){
            curr[j]={s[i-1][j],s[i][j],j};
        }
        sort(curr.begin(),curr.end(),p);
        a[i]=curr;
    }
    
    for(int i=0; i < n;i++){
        dp[m-1][i]={T[i],s[m-1][i],s[m-1][i]};
        temp[m-1][i]={s[m-2][i], s[m-1][i] , s[m-1][i]};
    } sort(temp[m-1].begin(),temp[m-1].end(),p);
    sort(dp[m-1].begin(),dp[m-1].end(),p);
    for(int i=m-2; i >=1; i--){
        for(int j=0; j < n;j++){
            dp[i][j]={T[j],s[i][j],dp[i+1][j].res};
            temp[i][j]={s[i-1][j],s[m-1][j],0};
            int l=i+1,r=m-1;
            int ii=-1,jj=-1;
            while(l<=r){
                int mid=(l+r)/2;
                int l1=0,r1=n-1;
                bool ok=false;
                ll length= station[mid] - station[i-1];
                ll start = s[i-1][j];
                ll expected = s[i-1][j] + (x * length);
                while(l1<=r1){
                    int mid1=(l1+r1)/2;
                    if(start > temp[mid][mid1].first && temp[mid][mid1].second > expected){
                        ok=true;
                        ii=mid;
                        jj=mid1;
                        r1=mid1-1;
                    } else if (start > temp[mid][mid1].first){
                        l1=mid1-1;
                    } else{
                        r1=mid1-1;
                    }
                }
                if(ok) r= mid-1;
                else l=mid+1;
            }
            if(ii!=-1){
                temp[i][j].res=temp[ii][jj].res;
                dp[i][j].res=temp[ii][jj].res;
            } else{
                ll finish=s[i][j] + ((station[m-1] - station[i]) *x);
                temp[i][j].res=dp[i][j].res=finish;
            }
        }
        sort(temp[i].begin(),temp[i].end(),p);
        sort(dp[i].begin(),dp[i].end(),p);
    }
}

long long arrival_time(long long Y)
{
    int l=1,r=m-1;
    int i=-1,j=-1;
    while(l<=r){
        int mid=(l+r)/2;
        int l1=0,r1=n-1;
        vector<item> curr=dp[mid];
        ll length=station[mid];
        ll expected = Y + (x*length);
        bool ok=false;
        while(l1 <= r1){
            int mid1=(l1+r1)/2;
            if(Y > curr[mid1].first && expected <= curr[mid1].second){
                i=mid,j=mid1;
                r1=mid1-1;
                ok=true;
            } else if ( curr[mid1].first > Y) r1=mid1-1;
            else l1=mid1+1;

        }
        if(ok) r=mid-1;
        else l=mid+1;
    }
    if(i==-1){
        // cout << 1 << endl;
        return (Y + (x*mx));
    }
    return dp[i][j].res;
}

// 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: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35