Submission #987543

#	Time	Username	Problem	Language	Result	Execution time	Memory
987543		vjudge1	Overtaking (IOI23_overtaking)	C++17	0 / 100	2 ms	2552 KiB

overtaking

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define pb push_back

using namespace std;

struct buses{
	ll m, b, i;
	ll eval(ll x){
		return m*x+b;
	}
	bool operator<(buses B){
		if(b==B.b) return m<B.m;
		return b<B.b;
	}
};

ll n, m, h, x, ti[1005][1005], tf[1005][1005], s[1005];

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, h=L, x=X, m=M;
	vector<buses> bus;
	rep(i,0,n) bus.pb({W[i],T[i],i});
	rep(i,0,m) s[i]=S[i];
	ll l=0, f[n];
	rep(j,0,m){
		sort(bus.begin(),bus.end());
		rep(i,0,n){
			bus[i].b=bus[i].eval(S[j]-l);
			if(i) bus[i].b=max(bus[i-1].b,bus[i].b);
			f[i]=bus[i].b;
		}
		rep(i,0,n){
			ti[j][i]=bus[i].b;
			tf[j][i]=bus[i].i;
		}
		l=S[j];
	}
	rep(j,0,m){
		rep(i,0,n){
			tf[j][i]=f[bus[i].i];
			if(i) tf[j][i]=max(tf[j][i-1],tf[j][i]);
		}
	}
}

long long arrival_time(long long Y){
	int l=0, r=m-1, mid, L, R, MID;
	ll dis;
	while(l<=r){
		mid=(l+r)>>1;
		dis=(x*s[mid])+Y;
		L=0, R=n-1;
		while(L<=R){
			MID=(L+R)>>1;
			if(ti[mid][MID]>=dis) R=MID-1;
			else L=MID+1;
		}
		if(L<n) dis=max(dis,ti[mid][L]);
		dis+=(h-s[mid])*x;
		if(L==n || tf[mid][R]<=dis) r=mid-1;
		else l=mid+1;
	}
	dis=(x*s[l])+Y;
	L=0, R=n-1;
	while(L<=R){
		MID=(L+R)>>1;
		if(ti[l][MID]>=dis) R=MID-1;
		else L=MID+1;
	}
	if(L) dis=max(dis,ti[l][L]);
	dis+=(h-s[l])*x;
	return dis;
}

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