제출 #879863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879863		SanguineChameleon	추월 (IOI23_overtaking)	C++17	39 / 100	3599 ms	63692 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;


long long off = 0;
set<pair<long long, pair<long long, long long>>> Ranges;

void init(int len, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
	vector<pair<long long, int>> cur_T;
	for (int i = 0; i < N; i++) {
		if (W[i] > X) {
			cur_T.emplace_back(T[i], W[i]);
		}
	}
	vector<pair<long long, long long>> queries;
	for (int i = 0; i < M - 1; i++) {
		sort(cur_T.begin(), cur_T.end());
		vector<pair<long long, int>> nxt_T(cur_T.size());
		int start = 0;
		long long mx = 0;
		int dist = S[i + 1] - S[i];
		for (int j = 0; j < (int)cur_T.size(); j++) {
			if (j > 0 && cur_T[j].first != cur_T[j - 1].first) {
				for (int k = start; k < j; k++) {
					mx = max(mx, nxt_T[k].first);
				}
				start = j;
			}
			nxt_T[j] = {max(mx, cur_T[j].first + 1LL * cur_T[j].second * dist), cur_T[j].second};
		}
		for (int j = (int)cur_T.size() - 1; j >= 0; j--) {
			queries.emplace_back(cur_T[j].first - off, nxt_T[j].first - off - 1LL * X * dist);
		}
		off += 1LL * X * dist;
		cur_T.swap(nxt_T);
	}
	for (auto [A, B]: queries) {
		A++;
		B--;
		if (A > B) {
			continue;
		}
		auto it = Ranges.lower_bound({A, {-1, -1}});
		if (it == Ranges.end()) {
			Ranges.emplace(B + 1, make_pair(A, B));
			continue;
		}
		long long L = min(it->second.first, A);
		long long R = min(B, it->second.first - 1);
		while (it->first <= B) {
			R = it->second.second;
			it = Ranges.erase(it);
			if (it == Ranges.end()) {
				R = B;
				break;
			}
			if (R < B) {
				R = min(B, it->second.first - 1);
			}
		}
		if (L <= R) {
			Ranges.emplace(B + 1, make_pair(L, R));
		}
	}
}

long long arrival_time(long long Y) {
	long long res = Y;
	for (auto [val, pos]: Ranges) {
		if (pos.first <= Y && Y <= pos.second) {
			res = val;
			break;
		}
	}
	res += off;
	return res;
}

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