Submission #844017

#	Time	Username	Problem	Language	Result	Execution time	Memory
844017		dong_liu	Overtaking (IOI23_overtaking)	C++17	100 / 100	1264 ms	111060 KiB

overtaking

#ifndef LOCAL
#include "overtaking.h"
#endif
#include "bits/stdc++.h"
using namespace std;

#ifndef LOCAL
#define cerr if(0)cerr
#endif

typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pi;

const int N=1e3+5,N_=1<<21;

struct B {ll s,t;int i;}b[N][N];
ll ans[N][N];
bool operator<(B a,B b){return a.s!=b.s?a.s<b.s:a.t<b.t;}

ll xx[N_];
int n_,k;
pi st[N_*2];

pi qry(ll x){
	int p=upper_bound(xx,xx+k,x)-xx-1;
	p+=n_;
	pi v{N,0};
	while(p>0)v=min(v,st[p]),p>>=1;
	return v;
}
void upd(ll l,ll r,pi x){
	if(l<=r){
		int ql=upper_bound(xx,xx+k,l)-xx-1;
		int qr=upper_bound(xx,xx+k,r)-xx-1;
		for(ql+=n_,qr+=n_;ql<=qr;ql>>=1,qr>>=1){
			if(ql&1)st[ql]=min(st[ql],x),ql++;
			if(~qr&1)st[qr]=min(st[qr],x),qr--;
		}
	}
}

ll l,x;

void init(int l_,int n,vector<ll>t,vi w,int x_,int m,vi s){
	l=l_,x=x_;
	for(int i=0;i<n;i++)b[0][i]={0,t[i],i};
	n_=0;
	for(int t=1;t<m;t++){
		for(int i=0;i<n;i++){
			auto[s_,t_,i_]=b[t-1][i];
			b[t][i]={t_,t_+1ll*w[i_]*(s[t]-s[t-1]),i_};
		}
		sort(b[t],b[t]+n);
		for(int i=1;i<n;i++)b[t][i].t=max(b[t][i].t,b[t][i-1].t);
		for(int i=0;i<n;i++){
			xx[n_++]=b[t][i].s-x*s[t-1]+1;
			xx[n_++]=b[t][i].t-x*s[t];
		}
	}
	xx[n_++]=-4e18;
	sort(xx,xx+n_);
	k=unique(xx,xx+n_)-xx;
	n_=1;while(n_<k)n_<<=1;
	for(int i=1;i<n_*2;i++)st[i]={N,0};
	for(int t=m-1;t>=1;t--){
		for(int i=0;i<n;i++){
			pi p=qry(b[t][i].t-x*s[t]);p.second*=-1;
			if(p==pi{N,0})ans[t][i]=b[t][i].t+x*(l-s[t]);
			else ans[t][i]=ans[p.first][p.second];
		}
		for(int i=0;i<n;i++)upd(b[t][i].s-x*s[t-1]+1,b[t][i].t-x*s[t]-1,pi{t,-i});
	}
}

ll arrival_time(ll t){
	pi p=qry(t);p.second*=-1;
	if(p==pi{N,0})return t+x*l;
	return ans[p.first][p.second];
}

#ifdef LOCAL
int main(){
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	int l,n,x,m,q;
	cin>>l>>n>>x>>m>>q;
	vector<ll> t(n);
	vi w(n),s(m);
	for(int i=0;i<n;i++)cin>>t[i];
	for(int i=0;i<n;i++)cin>>w[i];
	for(int i=0;i<m;i++)cin>>s[i];
	init(l,n,t,w,x,m,s);
	for(int h=1;h<=q;h++){
		ll t;
		cin>>t;
		cout<<"query t="<<t<<" got "<<arrival_time(t)<<'\n';
	}
}
#endif

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