Submission #1233851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233851		AMnu	Overtaking (IOI23_overtaking)	C++20	39 / 100	2245 ms	2162688 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const ll INF = 2e18;

ll sh;

struct tree {
	ll val, L, R, mid;
	tree *lef, *rig;
	
	tree(ll x,ll y) {
		val = 0;
		L = x; R = y;
		mid = (L+R)/2;
		lef = rig = 0;
	}
	
	ll query(ll x) {
		ll ans = max(x,val);
		if (x <= mid && lef) {
			ans = max(ans,lef->query(x));
		}
		if (x > mid && rig) {
			ans = max(ans,rig->query(x));
		}
		return ans;
	}
	
	void push() {
		if (!lef) {
			lef = new tree(L,mid);
			rig = new tree(mid+1,R);
		}
	}
	
	void update(ll x,ll y,ll z) {
		if (x <= L && y >= R) {
			val = z;
			lef = rig = 0;
			return;
		}
		if (x > R || y < L) {
			return;
		}
		push();
		lef->update(x,y,z);
		rig->update(x,y,z);
	}
} root(1,INF);

void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S) {
	sh = (ll)X*L;
	vector <pii> V;
	for (int i=0;i<N;i++) {
		if (W[i] > X) {
			V.push_back({T[i]+sh,W[i]-X});
		}
	}
	N = V.size();
	if (!N) {
		return;
	}
	vector <pii> U;
	for (int i=1;i<M;i++) {
		int s = S[i]-S[i-1];
		sort(V.begin(),V.end());
		for (int i=0;i<N;i++) {
			V[i].fi += V[i].se*s;
		}
		for (int i=1;i<N;i++) {
			V[i].fi = max(V[i].fi,V[i-1].fi);
		}
		for (int i=N-1;i>=0;i--) {
			U.push_back({V[i].fi-V[i].se*s,V[i].fi});
		}
	}
	reverse(U.begin(),U.end());
	for (pii u : U) {
		root.update(u.fi+1,u.se-1,root.query(u.se));
	}
}

long long arrival_time(ll Y) {
	return root.query(Y+sh);
}

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