Submission #845775

#	Time	Username	Problem	Language	Result	Execution time	Memory
845775		Pajaraja	Overtaking (IOI23_overtaking)	C++17	100 / 100	2819 ms	102916 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define MAXN 1007
using namespace std;
long long l,x;
vector<long long> t,w,s,poz[MAXN];
vector<int> koji[MAXN];
int n,m;
map<pair<int,long long> ,long long> mp;
int manjih(long long val,int ind)
{
    if(n==0) return 0;
    if(poz[ind][0]>=val) return 0;
    int l=0,r=n-1;
    while(l!=r)
    {
        int sr=(l+r+1)/2;
        if(poz[ind][sr]<val) l=sr;
        else r=sr-1;
    }
    return l+1;}
pair<int,long long> next(int stan, long long vreme)
{
    int br=manjih(vreme,stan);
    if(manjih(vreme+x*(l-s[stan]),m-1)==br) return {m-1,vreme+x*(l-s[stan])};
    int l=stan+1,r=m-1;
    while(l!=r)
    {
        int sr=(l+r)/2;
        long long novo=vreme+x*(s[sr]-s[stan]);
        if(manjih(novo,sr)!=br) r=sr;
        else l=sr+1;
    }
    return {l,poz[l][br-1]};
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    l=L; x=X; m=M; n=N;
    for(int i=0;i<M;i++) s.push_back(S[i]);
    for(int i=0;i<N;i++)
    {
        if(W[i]<X) n--;
        else
        {
            w.push_back(W[i]);
            t.push_back(T[i]);
        }
    }
    vector<pair<long long,int>> zs;
    for(int i=0;i<n;i++) zs.push_back({t[i],i});
    sort(zs.begin(),zs.end());
    for(int i=0;i<n;i++) poz[0].push_back(zs[i].first);
    for(int i=0;i<n;i++) koji[0].push_back(zs[i].second);
    for(int j=1;j<m;j++)
    {
        vector<pair<long long,int> > v;
        long long tmax=0,cmax=0;
        for(int i=0;i<n;i++)
        {
            if(i!=0 && poz[j-1][i]!=poz[j-1][i-1]) cmax=tmax;
            long long ar=poz[j-1][i]+w[koji[j-1][i]]*(s[j]-s[j-1]);
            tmax=max(tmax,ar);
            v.push_back({max(ar,cmax),koji[j-1][i]});
        }
        sort(v.begin(),v.end());
        for(int i=0;i<n;i++) poz[j].push_back(v[i].first);
        for(int i=0;i<n;i++) koji[j].push_back(v[i].second);
    }
    for(int j=m-1;j>=0;j--) for(int i=0;i<n;i++)
    {
        pair<int,long long> pill=next(j,poz[j][i]);
        if(pill.first==m-1) mp[{j,poz[j][i]}]=pill.second;
        else mp[{j,poz[j][i]}]=mp[pill];
    }
    return;
}

long long arrival_time(long long Y)
{
    pair<int,long long> pill=next(0,Y);
    if(pill.first==m-1) return pill.second;
    else return mp[pill];
}

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