Submission #846434

#	Time	Username	Problem	Language	Result	Execution time	Memory
846434		denniskim	Overtaking (IOI23_overtaking)	C++17	10 / 100	3 ms	4952 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, x, m;
ll t[1010];
ll w[1010];
ll cc;
pll a[1010][1010];
ll tmp[1010];
ll TM[1010][1010];
ll s[1010];
vector<pll> vv[1010];
vector<ll> num[1010];

struct gujo
{
	ll L, R, ok, gap;
};

vector<gujo> ans;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
	n = N;
	x = X;
	m = M;
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(W[i] <= X)
			continue;
		
		t[cc] = T[i];
		w[cc++] = W[i];
	}
	
	for(ll i = 0 ; i < m ; i++)
		s[i] = S[i];
	
	n = cc;
	
	for(ll i = 0 ; i < n ; i++)
		a[0][i] = {t[i], w[i]};
	
	sort(a[0], a[0] + n);
	
	ll ccc = 0;
	
	for(ll i = 0 ; i < m - 1 ; i++)
	{
		vector<pll> vec, evec;
		vector<ll> vec2;
		ll dist = s[i + 1] - s[i];
		
		for(ll j = 0 ; j < n ; j++)
		{
			ll TT = a[i][j].fi;
			ll WW = a[i][j].se;
			
			TM[i][j] = TT + WW * dist;
			vec.push_back({TT + 1, j});
			evec.push_back({TT + (WW - x) * dist, j});
			vec2.push_back(TT + 1);
			vec2.push_back(TT + (WW - x) * dist);
		}
		
		vec2.push_back(0);
		sort(vec.begin(), vec.end());
		sort(evec.begin(), evec.end());
		compress(vec2);
		
		multiset<ll> st;
		ll p1 = 0, p2 = 0;
		
		for(auto &j : vec2)
		{
			while(p1 < (ll)vec.size() && vec[p1].fi <= j)
			{
				st.insert(TM[i][vec[p1].se]);
				p1++;
			}
			
			while(p2 < (ll)evec.size() && evec[p2].fi <= j)
			{
				st.erase(st.find(TM[i][evec[p2].se]));
				p2++;
			}
			
			if(!st.empty())
				vv[i].push_back({j, (*st.rbegin())});
			else
				vv[i].push_back({j, -1});
			
			num[i].push_back(++ccc);
		}
		
		stack<pll> stk;
		
		for(ll j = n - 1 ; j >= 0 ; j--)
		{
			while(!stk.empty() && stk.top().fi <= TM[i][j])
				stk.pop();
			
			stk.push({TM[i][j], j});
		}
		
		vector<ll> idx;
		
		while(!stk.empty())
		{
			idx.push_back(stk.top().se);
			stk.pop();
		}
		
		idx.push_back(n);
		
		for(ll j = 0 ; j < (ll)idx.size() - 1 ; j++)
		{
			for(ll k = idx[j] ; k < idx[j + 1] ; k++)
				tmp[k] = TM[i][idx[j]];
		}
		
		for(ll j = 0 ; j < n ; j++)
			a[i + 1][j] = {tmp[j], a[i][j].se};
		
		sort(a[i + 1], a[i + 1] + n);
	}
	
	vector<gujo> vec;
	
	for(ll i = 0 ; i < (ll)vv[m - 2].size() ; i++)
	{
		gujo tmp;
		
		tmp.L = vv[m - 2][i].fi;
		
		if(i == (ll)vv[m - 2].size() - 1)
			tmp.R = INF;
		else
			tmp.R = vv[m - 2][i + 1].fi - 1;
		
		if(vv[m - 2][i].se != -1)
			tmp.ok = 1, tmp.gap = vv[m - 2][i].se;
		else
			tmp.ok = 0, tmp.gap = (s[m - 1] - s[m - 2]) * x;
		
		vec.push_back(tmp);
	}
	
	for(ll i = m - 3 ; i >= 0 ; i--)
	{
		vector<gujo> tvec;
		
		for(ll j = 0 ; j < (ll)vv[i].size() ; j++)
		{
			gujo tmp;
			ll L = vv[i][j].fi;
			ll R = 0;
			
			if(j == (ll)vv[i].size() - 1)
				R = INF;
			else
				R = vv[i][j + 1].fi - 1;
			
			tmp.L = L, tmp.R = R;
			
			if(vv[i][j].se != -1)
			{
				ll l = 0, r = (ll)vec.size() - 1;
				
				while(l <= r)
				{
					ll mid = (l + r) >> 1;
					
					if(vec[mid].L <= vv[i][j].se)
						l = mid + 1;
					else
						r = mid - 1;
				}
				
				if(vec[r].ok)
					tmp.ok = 1, tmp.gap = vec[r].gap;
				else
					tmp.ok = 1, tmp.gap = vv[i][j].se + vec[r].gap;
				
				tvec.push_back(tmp);
				continue;
			}
			
			L += (s[i + 1] - s[i]) * x;
			R += (s[i + 1] - s[i]) * x;
			
			ll l = 0, r = (ll)vec.size() - 1;
			ll lidx, ridx;
			
			while(l <= r)
			{
				ll mid = (l + r) >> 1;
				
				if(vec[mid].L <= L)
					l = mid + 1;
				else
					r = mid - 1;
			}
			
			lidx = r;
			
			l = 0, r = (ll)vec.size() - 1;
			
			while(l <= r)
			{
				ll mid = (l + r) >> 1;
				
				if(vec[mid].L <= R)
					l = mid + 1;
				else
					r = mid - 1;
			}
			
			ridx = r;
			
			ll last = L;
			
			for(ll k = lidx ; k <= ridx ; k++)
			{
				tmp.L = last - (s[i + 1] - s[i]) * x;
				tmp.R = min(R, vec[k].R) - (s[i + 1] - s[i]) * x;
				
				if(vec[k].ok)
					tmp.ok = 1, tmp.gap = vec[k].gap;
				else
					tmp.ok = 0, tmp.gap = vec[k].gap + (s[i + 1] - s[i]) * x;
				
				tvec.push_back(tmp);
				last = vec[k].R + 1;
			}
		}
		
		gujo tmp;
		
		if(tvec.empty())
			assert(0);
		
		tmp = tvec[0];
		vec.clear();
		
		for(ll i = 1 ; i < (ll)tvec.size() ; i++)
		{
			if(tvec[i].ok == tmp.ok && tvec[i].gap == tmp.gap)
				tmp.R = max(tmp.R, tvec[i].R);
			
			else
			{
				vec.push_back(tmp);
				tmp = tvec[i];
			}
		}
		
		vec.push_back(tmp);
		
		if((ll)vec.size() >= 3 * n)
			assert(0);
	}
	
	ans = vec;
}

ll arrival_time(ll Y)
{
	ll l = 0, r = (ll)ans.size() - 1;
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		
		if(ans[mid].L <= Y)
			l = mid + 1;
		else
			r = mid - 1;
	}
	
	if(!ans[r].ok)
		return ans[r].gap + Y;
	
	return ans[r].gap;
}

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