Submission #846112

#	Time	Username	Problem	Language	Result	Execution time	Memory
846112		denniskim	Overtaking (IOI23_overtaking)	C++17	0 / 100	7 ms	35420 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())

vector<pll> vec[1000010];
pll rng[1000010];
ll cc;
ll n, m, x;
pll a[1010];
vector<ll> in;
ll deg[1000010], dp[1000010];
vector< pair<pll, ll> > ans;
ll stp[1000010];
ll s[1000010];
ll t[1000010];

bool comp(pll X, pll Y)
{
	return X.se < Y.se;
}

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
	n = N;
	m = M;
	x = X;
	
	ll ccc = 0;
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(W[i] <= X)
			continue;
		
		a[ccc] = {W[i], T[i]};
		ccc++;
	}
	
	T[ccc] = 2000000000000000000;
	a[ccc++] = {X + 1, 2000000000000000000};
	
	for(ll i = 0 ; i < m ; i++)
		s[i] = S[i];
	
	n = ccc;
	
	for(ll i = 0 ; i < n ; i++)
		t[i] = T[i];
	
	sort(a, a + n, comp);
	
	vector<pll> last;
	
	for(ll i = 1 ; i < m ; i++)
	{
		ll dist = S[i] - S[i - 1];
		stack<pll> stk;
		
		for(ll j = n - 1 ; j >= 0 ; j--)
		{
			while(!stk.empty() && stk.top().fi <= a[j].fi * dist + a[j].se)
				stk.pop();
			
			stk.push({a[j].fi * dist + a[j].se, j});
		}
		
		vector<ll> num;
		
		while(!stk.empty())
		{
			num.push_back(stk.top().se);
			stk.pop();
		}
		
		vector<pll> tmtmp;
		
		if(!last.empty())
		{
			ll p = 0;
			
			for(ll j = 0 ; j < num.size() ; j++)
			{
				while(p < (ll)last.size() && last[p].fi <= num[j])
					p++;
				
				if(p == (ll)last.size())
					break;
				
				cc++;
				deg[last[p].se]++;
				vec[cc].push_back({last[p].se, a[num[j]].fi * dist + a[num[j]].se});
				tmtmp.push_back({num[j], cc});
			}
			
			last = tmtmp;
		}
		
		else
		{
			for(ll j = 0 ; j < (ll)num.size() ; j++)
			{
				cc++;
				last.push_back({num[j], cc});
			}
			
			in = num;
		}
		
		num.push_back(n);
		
		for(ll j = 0 ; j < (ll)num.size() - 1 ; j++)
		{
			ll gap = a[num[j]].fi * dist + a[num[j]].se;
			sort(a + num[j], a + num[j + 1]);
			
			for(ll k = num[j] ; k < num[j + 1] ; k++)
				a[k].se = gap;
		}
	}
	
	queue<ll> q;
	
	for(ll i = 1 ; i <= cc ; i++)
	{
		if(!deg[i])
			q.push(i);
	}
	
	while(!q.empty())
	{
		ll qq = q.front();
		q.pop();
		
		for(auto &i : vec[qq])
		{
			dp[i.fi] = max(dp[i.fi], max(dp[qq], i.se));
			deg[i.fi]--;
			stp[i.fi] = stp[qq] + 1;
			
			if(!deg[i.fi])
				q.push(i.fi);
		}
	}
	
	for(ll i = 0 ; i < (ll)in.size() ; i++)
		ans.push_back({{dp[i + 1], in[i]}, stp[i + 1]});
	
	return;
}

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

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:96:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(ll j = 0 ; j < num.size() ; j++)
      |                   ~~^~~~~~~~~~~~

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