Submission #220216

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
220216	2020-04-07T10:56:56 Z	atoiz	Harvest (JOI20_harvest)	C++14	100 / 100	776 ms	117560 KB

harvest

/*input
4 4 12 1
3 2 7 5 
0 1 9 8 
1
2 6

*/

#include <iostream>
#include <vector>
#include <algorithm> 
#include <cassert>
#include <ctime>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

const int INF = 2 * 1000 * 1000 * 1000 + 9;

using pii = pair<int64_t, int>;	

using ordered_set = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;
int ordered_counter = 0;
void set_insert(ordered_set &os, int64_t x)
{ os.insert(make_pair(x, ++ordered_counter)); }
int get_order(ordered_set &os, int64_t x)
{ return (int) os.order_of_key(make_pair(x, 0)); }

#define for_range(var, from, to) for (auto var = from; var < to; ++var)
#define for_each(var, list) for (auto &var : list)
#define all(list) begin(list), end(list)

int num_apples, num_employees, num_queries;
vector<int> pos_apples, pos_employees;
vector<vector<pii>> queries;
vector<int64_t> answers;
int perimeter, revive;

vector<pii> next_employee;
vector<vector<pii>> graph;
vector<vector<pii>> harvest_apples;
vector<bool> in_cycle;

void init_relations()
{
	vector<pii> timestamps_employee;
	timestamps_employee.reserve(2 * num_employees);
	for_range(employee, 0, num_employees) {
		timestamps_employee.emplace_back(pos_employees[employee], employee);
		timestamps_employee.emplace_back(pos_employees[employee] + perimeter, employee);
	}
	sort(all(timestamps_employee));

	// init next_employee
	next_employee.resize(num_employees);
	graph.assign(num_employees, vector<pii>(0));

	int revive_dist = revive % perimeter;
	int64_t revive_add = revive - revive_dist;
	for_range(time_id, num_employees, 2 * num_employees) {
		auto cur = timestamps_employee[time_id];
		int pos = cur.first, employee = cur.second;
		auto it = prev(upper_bound(all(timestamps_employee), pii(pos - revive_dist, INF)));

		int64_t wait_time = pos - it->first + revive_add;
		assert(wait_time >= revive);
		int next_id = it->second;
		next_employee[employee] = make_pair(wait_time, next_id);
		graph[next_id].emplace_back(wait_time, employee);

		// cout << "next " << employee << ": " << wait_time << ' ' << next_id << endl;
	}

	// init harvest_apples
	harvest_apples.assign(num_employees, vector<pii>(0));
	for_range(apple, 0, num_apples) {
		int pos = pos_apples[apple] + perimeter;
		auto it = prev(upper_bound(all(timestamps_employee), pii(pos, INF)));

		int wait_time = pos - it->first;
		int employee = it->second;
		harvest_apples[employee].emplace_back(wait_time, apple);

		// cout << "harvest " << employee << ": " << wait_time << endl;
	}
}

void find_cycles()
{
	in_cycle.assign(num_employees, false);
	vector<int> color(num_employees, 0);

	for_range(start_employee, 0, num_employees) {
		for (int employee = start_employee; color[employee] != 2; employee = next_employee[employee].second) {
			++color[employee];
			if (color[employee] == 2) in_cycle[employee] = true;
		}

		for (int employee = start_employee; color[employee] != 2; employee = next_employee[employee].second) {
			++color[employee];
		}
	}

	for_range(employee, 0, num_employees) {
		if (in_cycle[employee]) {
			for (auto it = graph[employee].begin(); it != graph[employee].end(); ++it) {
				if (in_cycle[it->second]) {
					graph[employee].erase(it);
					break;
				}
			}
		}
	}
}

vector<ordered_set> all_apples;
vector<int64_t> dist_inc;
void solve_tree(int cur_employee)
{
	for_each(edge, graph[cur_employee]) {
		int64_t dist = edge.first;
		int child_employee = edge.second;

		solve_tree(child_employee);
		dist_inc[child_employee] += dist;

		if (all_apples[cur_employee].size() < all_apples[child_employee].size()) {
			all_apples[cur_employee].swap(all_apples[child_employee]);
			swap(dist_inc[cur_employee], dist_inc[child_employee]);
		}

		for_each(apple, all_apples[child_employee]) {
			set_insert(all_apples[cur_employee], apple.first + dist_inc[child_employee] - dist_inc[cur_employee]);
		}
	}

	for_each(harvest, harvest_apples[cur_employee]) {
		set_insert(all_apples[cur_employee], harvest.first - dist_inc[cur_employee]);
	}

	for_each(query, queries[cur_employee]) {
		int64_t time = query.first;
		int id = query.second;

		answers[id] = get_order(all_apples[cur_employee], time - dist_inc[cur_employee]);
	}
}
void solve_all_trees()
{
	all_apples.assign(num_employees, ordered_set());
	dist_inc.assign(num_employees, 0);
	for_range(employee, 0, num_employees) {
		if (in_cycle[employee]) {
			solve_tree(employee);
		}
	}
}

void solve_cycle(vector<int> cycle)
{
	reverse(all(cycle));
	// for_each(employee, cycle) cout << employee << ' '; cout << endl;

	int cycle_size = (int) cycle.size();

	int64_t cycle_perimeter = 0;
	for_each(employee, cycle) cycle_perimeter += next_employee[employee].first;
	assert(cycle_perimeter % perimeter == 0);
	// cout << "perimeter " << cycle_perimeter << endl;

	vector<int64_t> relative_position(cycle_size, 0);
	for_range(cycle_id, 1, cycle_size) {
		relative_position[cycle_id] = relative_position[cycle_id - 1] + next_employee[cycle[cycle_id]].first;
	}

	// reset answers from tree solver
	for_each(employee, cycle) {
		for_each(query, queries[employee]) {
			answers[query.second] = 0;
		}
	}

	// prepare
	vector<int64_t> apple_times;
	vector<pair<int64_t, int>> cur_queries;

	for_range(cycle_id, 0, cycle_size) {
		int employee = cycle[cycle_id];
		int64_t pos_inc = relative_position[cycle_id];

		for_each(apple, all_apples[employee]) {
			apple_times.push_back(apple.first + dist_inc[employee] + pos_inc);
			// cout << apple.first + dist_inc[employee] << ' ' << pos_inc << endl;
		}

		for_each(query, queries[employee]) {
			cur_queries.emplace_back(query.first + pos_inc, query.second);
			// cout << query.first << ' ' << pos_inc << endl;
		}
	}
	sort(all(apple_times));
	sort(all(cur_queries));

	// remove unwanted count from previous (position-wise) employee
	{
		ordered_set cur_state;
		for_range(cycle_id, 0, cycle_size) {
			int employee = cycle[cycle_id];
			int64_t pos_inc = relative_position[cycle_id];

			// update answers
			for_each(query, queries[employee]) {
				answers[query.second] -= get_order(cur_state, query.first + pos_inc);
			}

			// update cur_state
			for_each(apple, all_apples[employee]) {
				set_insert(cur_state, apple.first + dist_inc[employee] + pos_inc);
			}
		}
	}

	// add extra count from x % C < T % C
	{
		ordered_set cur_state;
		auto apple_it = apple_times.begin();
		for_each(query, cur_queries) {
			int64_t query_time = query.first;
			for (; apple_it != apple_times.end() && *apple_it < query_time; ++apple_it) {
				set_insert(cur_state, *apple_it % cycle_perimeter);
			}

			answers[query.second] += get_order(cur_state, query_time % cycle_perimeter);
		}
	}

	// add main count
	{
		auto apple_it = apple_times.begin();
		int64_t apple_count = 0, excludant = 0;

		for_each(query, cur_queries) {
			int64_t query_time = query.first;
			for (; apple_it != apple_times.end() && *apple_it < query_time; ++apple_it) {
				++apple_count, excludant += *apple_it / cycle_perimeter;
			}

			answers[query.second] += apple_count * (query_time / cycle_perimeter) - excludant;
		}
	}
}
void solve_all_cycles()
{
	vector<bool> visited(num_employees, false);
	for_range(start_employee, 0, num_employees) {
		if ((not in_cycle[start_employee]) or visited[start_employee]) continue;
		vector<int> cur_cycle;
		for (int employee = start_employee; not visited[employee]; employee = next_employee[employee].second) {
			cur_cycle.push_back(employee);
			visited[employee] = true;
		}
		solve_cycle(cur_cycle);
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> num_employees >> num_apples >> perimeter >> revive;
	pos_apples.resize(num_apples), pos_employees.resize(num_employees);
	for_each(pos, pos_employees) cin >> pos;
	for_each(pos, pos_apples) cin >> pos;

	cin >> num_queries;
	queries.assign(num_employees, vector<pii>(0));
	answers.resize(num_queries);
	for_range(query_id, 0, num_queries) {
		int employee;
		int64_t time;
		cin >> employee >> time;
		--employee;
		queries[employee].emplace_back(time + 1, query_id);
	}

	init_relations();
	find_cycles();
	solve_all_trees();
	solve_all_cycles();

	for_range(query_id, 0, num_queries) {
		cout << answers[query_id] << '\n';
	}
	// cout << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	640 KB	Output is correct
2	Correct	10 ms	1536 KB	Output is correct
3	Correct	11 ms	1664 KB	Output is correct
4	Correct	11 ms	1920 KB	Output is correct
5	Correct	11 ms	2048 KB	Output is correct
6	Correct	10 ms	2048 KB	Output is correct
7	Correct	10 ms	2176 KB	Output is correct
8	Correct	10 ms	1792 KB	Output is correct
9	Correct	10 ms	1792 KB	Output is correct
10	Correct	10 ms	1792 KB	Output is correct
11	Correct	10 ms	1792 KB	Output is correct
12	Correct	11 ms	1792 KB	Output is correct
13	Correct	11 ms	1792 KB	Output is correct
14	Correct	14 ms	1664 KB	Output is correct
15	Correct	11 ms	1920 KB	Output is correct
16	Correct	10 ms	2048 KB	Output is correct
17	Correct	11 ms	2048 KB	Output is correct
18	Correct	10 ms	1920 KB	Output is correct
19	Correct	10 ms	1920 KB	Output is correct
20	Correct	10 ms	1920 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	166 ms	12000 KB	Output is correct
2	Correct	286 ms	53632 KB	Output is correct
3	Correct	316 ms	53124 KB	Output is correct
4	Correct	320 ms	60532 KB	Output is correct
5	Correct	267 ms	78976 KB	Output is correct
6	Correct	274 ms	79108 KB	Output is correct
7	Correct	229 ms	50412 KB	Output is correct
8	Correct	237 ms	50376 KB	Output is correct
9	Correct	353 ms	66024 KB	Output is correct
10	Correct	267 ms	70128 KB	Output is correct
11	Correct	423 ms	71300 KB	Output is correct
12	Correct	415 ms	71428 KB	Output is correct
13	Correct	431 ms	71532 KB	Output is correct
14	Correct	321 ms	69048 KB	Output is correct
15	Correct	351 ms	67008 KB	Output is correct
16	Correct	273 ms	72836 KB	Output is correct
17	Correct	256 ms	72580 KB	Output is correct
18	Correct	156 ms	27352 KB	Output is correct
19	Correct	160 ms	27220 KB	Output is correct
20	Correct	244 ms	59908 KB	Output is correct

Subtask #3

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	640 KB	Output is correct
2	Correct	10 ms	1536 KB	Output is correct
3	Correct	11 ms	1664 KB	Output is correct
4	Correct	11 ms	1920 KB	Output is correct
5	Correct	11 ms	2048 KB	Output is correct
6	Correct	10 ms	2048 KB	Output is correct
7	Correct	10 ms	2176 KB	Output is correct
8	Correct	10 ms	1792 KB	Output is correct
9	Correct	10 ms	1792 KB	Output is correct
10	Correct	10 ms	1792 KB	Output is correct
11	Correct	10 ms	1792 KB	Output is correct
12	Correct	11 ms	1792 KB	Output is correct
13	Correct	11 ms	1792 KB	Output is correct
14	Correct	14 ms	1664 KB	Output is correct
15	Correct	11 ms	1920 KB	Output is correct
16	Correct	10 ms	2048 KB	Output is correct
17	Correct	11 ms	2048 KB	Output is correct
18	Correct	10 ms	1920 KB	Output is correct
19	Correct	10 ms	1920 KB	Output is correct
20	Correct	10 ms	1920 KB	Output is correct
21	Correct	166 ms	12000 KB	Output is correct
22	Correct	286 ms	53632 KB	Output is correct
23	Correct	316 ms	53124 KB	Output is correct
24	Correct	320 ms	60532 KB	Output is correct
25	Correct	267 ms	78976 KB	Output is correct
26	Correct	274 ms	79108 KB	Output is correct
27	Correct	229 ms	50412 KB	Output is correct
28	Correct	237 ms	50376 KB	Output is correct
29	Correct	353 ms	66024 KB	Output is correct
30	Correct	267 ms	70128 KB	Output is correct
31	Correct	423 ms	71300 KB	Output is correct
32	Correct	415 ms	71428 KB	Output is correct
33	Correct	431 ms	71532 KB	Output is correct
34	Correct	321 ms	69048 KB	Output is correct
35	Correct	351 ms	67008 KB	Output is correct
36	Correct	273 ms	72836 KB	Output is correct
37	Correct	256 ms	72580 KB	Output is correct
38	Correct	156 ms	27352 KB	Output is correct
39	Correct	160 ms	27220 KB	Output is correct
40	Correct	244 ms	59908 KB	Output is correct
41	Correct	699 ms	115196 KB	Output is correct
42	Correct	405 ms	76792 KB	Output is correct
43	Correct	288 ms	63600 KB	Output is correct
44	Correct	759 ms	90736 KB	Output is correct
45	Correct	522 ms	116076 KB	Output is correct
46	Correct	564 ms	116992 KB	Output is correct
47	Correct	598 ms	117560 KB	Output is correct
48	Correct	555 ms	116100 KB	Output is correct
49	Correct	580 ms	117256 KB	Output is correct
50	Correct	607 ms	101356 KB	Output is correct
51	Correct	697 ms	100436 KB	Output is correct
52	Correct	706 ms	98712 KB	Output is correct
53	Correct	735 ms	98052 KB	Output is correct
54	Correct	661 ms	98600 KB	Output is correct
55	Correct	776 ms	98052 KB	Output is correct
56	Correct	652 ms	110084 KB	Output is correct
57	Correct	604 ms	110724 KB	Output is correct
58	Correct	636 ms	111436 KB	Output is correct
59	Correct	597 ms	109444 KB	Output is correct
60	Correct	559 ms	109956 KB	Output is correct
61	Correct	607 ms	110468 KB	Output is correct
62	Correct	664 ms	92160 KB	Output is correct
63	Correct	494 ms	57684 KB	Output is correct
64	Correct	476 ms	58072 KB	Output is correct
65	Correct	469 ms	57980 KB	Output is correct
66	Correct	529 ms	57168 KB	Output is correct
67	Correct	457 ms	57268 KB	Output is correct
68	Correct	514 ms	56656 KB	Output is correct
69	Correct	665 ms	113924 KB	Output is correct
70	Correct	592 ms	108420 KB	Output is correct
71	Correct	702 ms	114052 KB	Output is correct
72	Correct	720 ms	116612 KB	Output is correct