Submission #846269

#	Time	Username	Problem	Language	Result	Execution time	Memory
846269		denniskim	Overtaking (IOI23_overtaking)	C++17	65 / 100	3519 ms	57920 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];

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);
	
	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});
		}
		
		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);
	}
}

ll arrival_time(ll Y)
{
	ll ret = Y;
	
	for(ll i = 0 ; i < m - 1 ; i++)
	{
		ll l = 0, r = (ll)vv[i].size() - 1;
		
		while(l <= r)
		{
			ll mid = (l + r) >> 1;
			
			if(vv[i][mid].fi <= ret)
				l = mid + 1;
			else
				r = mid - 1;
		}
		
		if(vv[i][r].se == -1)
			ret += (s[i + 1] - s[i]) * x;
		else
			ret = vv[i][r].se;
	}
	
	return ret;
}

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