제출 #916136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916136		redstonegamer22	추월 (IOI23_overtaking)	C++17	19 / 100	3582 ms	2252 KiB

overtaking

#ifndef LOCAL
	#include "overtaking.h"
#endif // LOCAL
#ifdef LOCAL
	#define _GLIBCXX_DEBUG
	#include <vector>

	void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S);

	long long arrival_time(long long Y);
#endif // LOCAL

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int time_infty = 1e18 + 7;
const int nmax = 1000 + 24;
const int nmax_bs_step = (1 << 10);

struct bus {
	int start_time;
	int speed;
};

vector<bus> glob_busses;
vector<vector<bus>> busses_by_station;
vector<vector<int>> endtime_of_bus_by_station;
vector<int> stations;
int X_init;

void precompute_strips() {
	// pentru fiecare statie, retin autobuzele ca perechi de (timp, viteza)
	auto busses = glob_busses;

	sort(busses.begin(), busses.end(), [](bus a, bus b) {
		if(a.start_time != b.start_time) 
			return a.start_time < b.start_time;
		return a.speed < b.speed;
	});

	busses_by_station.push_back(busses); // pentru statia 0

	for(int i = 0; i + 1 < stations.size(); i++) {
		int distance = stations[i + 1] - stations[i];

		int max_prefix = -1e9;

		vector<bus> new_busses;
		vector<int> new_endtime_of_bus;
		for(auto b : busses) {
			max_prefix = max(max_prefix, b.start_time + distance * b.speed);
			new_busses.push_back({max_prefix, b.speed});

			new_endtime_of_bus.push_back(max_prefix);
		}

		endtime_of_bus_by_station.push_back(new_endtime_of_bus);

		busses = new_busses;

		sort(busses.begin(), busses.end(), [](bus a, bus b) {
			if(a.start_time != b.start_time) 
				return a.start_time < b.start_time;
			return a.speed < b.speed;
		});

		busses_by_station.push_back(busses);
	}
}

struct intervals {
	int start, end, actual_end;

	bool operator<(const intervals &other) const {
		if(start != other.start) return start < other.start;
		return end < other.end;
	}

	bool operator==(const intervals &other) const {
		return start == other.start && end == other.end;
	}
};
// daca eu ma aflu la timpul Y si Y intre [start, end], atunci
// eu voi termina la timpul end la final

set<intervals> solution_set;

long long arrival_time_fast(long long Y) {
	// care doar da query in structura curenta a solution_set-ului
	// si returneaza timpul de sosire

	solution_set.insert({-time_infty, -time_infty, -time_infty});
	solution_set.insert({time_infty, time_infty, time_infty});

	// cautam in solution_set intervalul care contine Y
	auto it = solution_set.lower_bound({Y, time_infty});
	if(it == solution_set.begin()) {
		// nu exista niciun interval care sa contina Y
		return Y;
	}

	intervals interval = *prev(it);

	if(Y < interval.start || Y > interval.end) {
		// nu exista niciun interval care sa contina Y
		return Y;
	}

	return interval.actual_end;
}

long long query_strip(int strip_index, long long Y) {
	// strip-ul se intinde de la stations[strip_index] la stations[strip_index + 1]

	// cautam in busses_by_station[strip_index] autobuzul care ma tine in spate

	// facem o cautare binara pentru ultimul autobuz care (conform comparatorului custom) este
	// mai mic decat mine

	const auto& busses = busses_by_station[strip_index]; // O(1)
	const auto& endtime_of_bus = endtime_of_bus_by_station[strip_index]; // O(1)

	int ok = -1;
	for(int step = nmax_bs_step; step >= 1; step /= 2) {
		while(ok + step < busses.size() && busses[ok + step].start_time < Y) {
			ok += step;
		}
	}

	if(ok == -1) {
		// nu exista niciun autobuz care sa ma tina in spate
		return Y;
	}

	if(endtime_of_bus[ok] < Y) {
		// nu exista niciun autobuz care sa ma tina in spate
		return Y;
	}

	return endtime_of_bus[ok];
}

void add_strip(int strip_index) {
	// adaugam un nou strip in solution_set
	// practic la final sa dam query(Y) <=> Y' = query_strip(strip_index, Y) si apoi Y'' = arrival_time_fast(Y')

	set<intervals> new_solution_set;
	new_solution_set.insert({-time_infty, -time_infty, -time_infty});

	// eu o sa observ ca in general un interval merge de la un bus.start_time + 1 pana la 
	// ????

	const auto& busses = busses_by_station[strip_index]; // O(1)

	vector<int> possible_starts;
	for(auto b : busses) {
		possible_starts.push_back(b.start_time + 1);
	}
	for(auto prev_interval : solution_set) {
		if(prev_interval.start == -time_infty) continue;
		if(prev_interval.start == time_infty) continue;

		possible_starts.push_back(prev_interval.start);
	}
	sort(possible_starts.begin(), possible_starts.end());

	for(auto start : possible_starts) {
		// int start = busses[i].start_time + 1;
		if(start <= new_solution_set.rbegin()->end) continue;
		// set.rbegin() este un pointer la ultimul element din set
		// daca ultimul interval pe care l-am calculat se termina inainte de startul nou
		// inseamna ca si acest start este parte din intervalul vechi
		
		int end = start;

		int total_query_start = arrival_time_fast(query_strip(strip_index, start));

		for(int step = (1LL << 60); step >= 1; step /= 2) {
			int total_query_end = arrival_time_fast(query_strip(strip_index, end + step));
			if(total_query_end == total_query_start) {
				end += step;
			}
		}

		new_solution_set.insert({start, end, total_query_start});
	}

	new_solution_set.insert({time_infty, time_infty, time_infty});

	solution_set = new_solution_set;
	return;
}

#undef int
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
#define int long long
	// scad X (viteza autobuzului de query) din fiecare viteza de autobuz (W)
	for(int i = 0; i < N; ++i) {
		W[i] -= X;
	}
	X_init = X;

	// initialize busses
	for(int i = 0; i < N; ++i) {
		bus b;
		b.start_time = T[i];
		b.speed = W[i];

		if(W[i] <= 0) continue; // acest autobuz nu afecteaza autobuzul meu!

		glob_busses.push_back(b);
	}

	// initialize stations
	for(int i = 0; i < M; ++i) {
		stations.push_back(S[i]);
	}

	precompute_strips();

	// initialize solution_set
	for(int i = stations.size() - 2; i >= 0; i--) {
		add_strip(i);

		#ifdef LOCAL
			cerr << "Added strip " << i << endl;
			for(auto pr : solution_set) {
				cerr << pr.start << " " << pr.end << " " << pr.actual_end << endl;
			}

			for(int wrong_Y = 0; wrong_Y < 10000; wrong_Y++) {
				long long fast_answer = arrival_time_fast(wrong_Y);
				long long slow_answer = wrong_Y;
				for(int j = i; j + 1 < stations.size(); j++) {
					slow_answer = query_strip(j, slow_answer);
				}
				if(fast_answer != slow_answer) {
					cerr << "wrong_Y: " << wrong_Y << endl;
					cerr << "Fast: " << fast_answer << endl;
					cerr << "Slow: " << slow_answer << endl;
					cerr << endl;

					assert(!"Not equal");
				}
			}
		#endif // LOCAL
	}
}

long long arrival_time_brut(long long Y) {
	auto busses = glob_busses;
	busses.push_back({Y, 0}); // autobuzul meu incepe la timpul Y si are viteza 0

	sort(busses.begin(), busses.end(), [](bus a, bus b) {
		if(a.start_time != b.start_time) 
			return a.start_time < b.start_time;
		return a.speed < b.speed;
	});

	for(int i = 0; i + 1 < stations.size(); i++) {
		int distance = stations[i + 1] - stations[i];

		int max_prefix = -1e9;

		vector<bus> new_busses;
		for(auto b : busses) {
			max_prefix = max(max_prefix, b.start_time + distance * b.speed);
			new_busses.push_back({max_prefix, b.speed});
		}

		busses = new_busses;

		sort(busses.begin(), busses.end(), [](bus a, bus b) {
			if(a.start_time != b.start_time) 
				return a.start_time < b.start_time;
			return a.speed < b.speed;
		});
	}

	for(auto b : busses) {
		if(b.speed == 0) return b.start_time;
	}

	assert(false); // nu se poate ajunge aici
}

long long arrival_time_slow(long long Y) {
	// repeatedly use query_strip()

	for(int strip_index = 0; strip_index + 1 < stations.size(); strip_index++) {
		Y = query_strip(strip_index, Y);
	}

	return Y;
}

long long arrival_time(long long Y) {
	long long answer = arrival_time_fast(Y);
	#ifdef LOCAL
		cerr << "Fast: " << answer << endl;
		cerr << "Slow: " << arrival_time_slow(Y) << endl;
		cerr << "Brut: " << arrival_time_brut(Y) << endl;
		assert (answer == arrival_time_slow(Y));
		assert (answer == arrival_time_brut(Y));
	#endif // LOCAL
	return answer + 1LL * (stations.back() - stations[0]) * X_init;
}

#ifdef LOCAL
#undef int
// Grader
#include <cassert>
#include <cstdio>
#include <vector>

int main()
{
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif // LOCAL

컴파일 시 표준 에러 (stderr) 메시지

overtaking.cpp: In function 'void precompute_strips()':
overtaking.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i + 1 < stations.size(); i++) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int query_strip(long long int, long long int)':
overtaking.cpp:127:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   while(ok + step < busses.size() && busses[ok + step].start_time < Y) {
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time_brut(long long int)':
overtaking.cpp:262:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |  for(int i = 0; i + 1 < stations.size(); i++) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time_slow(long long int)':
overtaking.cpp:292:43: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  292 |  for(int strip_index = 0; strip_index + 1 < stations.size(); strip_index++) {
      |                           ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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