Submission #1007867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007867		PotatoMan	Overtaking (IOI23_overtaking)	C++17	100 / 100	1071 ms	111188 KiB

overtaking

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

vector<ll> s;
vector<pair<ll,ll>> p;
ll l,n,x,m;
vector<vector<pair<pair<ll,ll>,int>>> ps(1005);
vector<vector<ll>> start(1005);
vector<pair<pair<ll,ll>,int>> cur;
ll pos = 0;
pair<ll,ll> pref[1005][1005];
ll dp[1005][1005];
ll h[1005][1005];

ll f(int xx,int y,ll hh){
	//cout<<"!"<<xx<<" "<<y<<" "<<hh<<"\n";
	if( y == m-1 ) return dp[xx][y] = hh;
	if( dp[xx][y] != 0 ) return dp[xx][y];
	int foo = lower_bound(start[y+1].begin(),start[y+1].end(),hh) - start[y+1].begin();
	int l = y+1,r = m;
	int res = inf;
	while( l <= r ){
		int tm = (l+r)/2;
		ll vh = hh+(s[tm-1]-s[y])*x;
		int vm = lower_bound(start[tm].begin(),start[tm].end(),vh) - start[tm].begin();
		//cout<<"? "<<tm<<" "<<vh<<" "<<vm<<" "<<foo<<"\n";
		if( vm < foo ){
			res = min(res,tm);
			r = tm-1;
		}
		else{
			l = tm+1;
		}
	}
	//cout<<"res :"<<res<<"\n";
	if( res == inf ){
		return dp[xx][y] = hh+(s.back()-s[y])*x;
	}
	foo = upper_bound(start[res-1].begin(),start[res-1].end(),hh+(s[res-2]-s[y])*x-1) - start[res-1].begin();
	//cout<<"foo :"<<hh+(s[res-2]-s[y])*x<<" "<<foo<<" "<<res<<"\n";
	return dp[xx][y] = f(pref[res-2][foo].second,res-1,h[pref[res-2][foo].second][res-1]);
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
	n = N;
	for(int i = 0 ; i < n ; i++) p.push_back({T[i],W[i]});
	for(auto u : S) s.push_back(u);
	l = L;
	x = X;
	m = M;
	for(int i = 0 ; i < n ; i++){
		if( p[i].second >= x ){
			h[cur.size()][0] = p[i].first;
			cur.push_back({p[i],cur.size()});
		}
	}
	//preprocessing
	n = cur.size();
	for(int i = 1 ; i < m ; i++){
		sort(cur.begin(),cur.end());
		ll mx = 0;
		for(int j = 0 ; j < n ; j++){
			start[i].push_back(cur[j].first.first);
			if( cur[j].first.first+(s[i]-pos)*cur[j].first.second <= mx ){
				ps[i].push_back({{cur[j].first.first,mx},cur[j].second});
				cur[j].first.first = mx;
				h[cur[j].second][i] = cur[j].first.first;
			}
			else{
				ps[i].push_back({{cur[j].first.first,cur[j].first.first+(s[i]-pos)*cur[j].first.second},cur[j].second});
				cur[j].first.first = cur[j].first.first+(s[i]-pos)*cur[j].first.second;
				mx = cur[j].first.first;
				h[cur[j].second][i] = cur[j].first.first;
			}
		}
		pos = s[i];
	}
	for(int i = 0 ; i < n ; i++) {
		start[m].push_back(cur[i].first.first);
	}
	for(int i = 1 ; i <= m ; i++) {
		sort(ps[i].begin(),ps[i].end());
		sort(start[i].begin(),start[i].end());
	}
	//~ cout<<"start\n";
	//~ for(int i = 0 ; i <= m ; i++){
		//~ for(auto u : start[i]) cout<<u<<" ";
		//~ cout<<"\n";
	//~ }
	//prefmax
	for(int i = 0 ; i < m ; i++){
		pref[i][0] = {0,0};
		for(int j = 1 ; j <= (int) ps[i+1].size() ; j++){
			if( ps[i+1][j-1].first.second > pref[i][j-1].first ){
				pref[i][j] = {ps[i+1][j-1].first.second,ps[i+1][j-1].second};
			}
			else pref[i][j] = pref[i][j-1];
			//cout<<"pref "<<i<<" "<<j<<" "<<pref[i][j].first<<" "<<pref[i][j].second<<"\n";
		}
	}
	//dp
	memset(dp,0,sizeof(dp));
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			f(i,j,h[i][j]);
			//cout<<"dp "<<i<<" "<<j<<" "<<h[i][j]<<" "<<dp[i][j]<<"\n";
		}
	}
    return;
}

long long arrival_time(long long Y)
{
	ll y = Y,ans;
	int foo = lower_bound(start[1].begin(),start[1].end(),y) - start[1].begin();
	int l = 1,r = m;
	int res = inf;
	while( l <= r ){
		int tm = (l+r)/2;
		ll vh = y+s[tm-1]*x;
		int vm = lower_bound(start[tm].begin(),start[tm].end(),vh) - start[tm].begin();
		//cout<<tm<<" "<<vh<<" "<<vm<<" "<<foo<<"\n";
		if( vm < foo ){
			res = min(res,tm);
			r = tm-1;
		}
		else{
			l = tm+1;
		}
	}
	if( res == inf ){
		ans = Y+s.back()*x;
		return ans;
	}
	foo = upper_bound(start[res-1].begin(),start[res-1].end(),y+s[res-2]*x-1) - start[res-1].begin();
	//cout<<"! "<<res<<" "<<foo<<"\n";
	return dp[pref[res-2][foo].second][res-1];
}

//~ 100 1 10 3 1
//~ 0
//~ 20
//~ 0 20 100
//~ 10

//~ 1000 1 20 6 1
//~ 0
//~ 100
//~ 0 1 2 3 4 5
//~ 210

//~ 10000 2 2 2 1
//~ 500 0
//~ 5 10
//~ 0 100
//~ 800

//~ 10000 2 10 2 2
//~ 0 100
//~ 100 100
//~ 0 100
//~ 10 101

//~ 6 4 10 4 2
//~ 20 10 40 0
//~ 5 20 20 30
//~ 0 1 3 6
//~ 0 50

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