Submission #748887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748887	2023-05-27T06:32:03 Z	wenqi	Ancient Books (IOI17_books)	C++17	50 / 100	1362 ms	146892 KB

books

#include "books.h"
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>

using namespace std;
using ll = long long;

bool seen[1000005];
vector<int> P;
vector<int> t;

struct Node
{
	int mn, mx;
};

Node nodes[8000005];
int gmn[1000005], gmx[1000005];

void upd(int i, int l, int r, int p, int mn, int mx)
{
	auto &node = nodes[i];
	if (p < l or p > r)
		return;
	if (l == r)
	{
		node.mn = min(node.mn, mn);
		node.mx = max(node.mx, mx);
		return;
	}
	int m = (l + r) / 2;
	upd(2 * i, l, m, p, mn, mx);
	upd(2 * i + 1, m + 1, r, p, mn, mx);
	node.mn = min(nodes[2 * i].mn, nodes[2 * i + 1].mn);
	node.mx = max(nodes[2 * i].mx, nodes[2 * i + 1].mx);
}

pair<int, int> query(int i, int l, int r, int ql, int qr)
{
	auto &node = nodes[i];
	if (qr < l or ql > r)
		return {1e9, 0};
	if (ql <= l and qr >= r)
		return {node.mn, node.mx};
	int m = (l + r) / 2;
	auto A = query(2 * i, l, m, ql, qr);
	auto B = query(2 * i + 1, m + 1, r, ql, qr);
	return {min(A.first, B.first), max(A.second, B.second)};
}

ll dfs(int i)
{
	if (seen[i])
		return 0;
	seen[i] = true;
	t.push_back(i);
	return abs(i - P[i]) + dfs(P[i]);
}

ll minimum_walk(vector<int> p, int s)
{
	P = p;
	ll sum = 0;
	int n = p.size();
	vector<pair<int, int>> q;
	vector<pair<pair<int, int>, int>> Q, Q2;
	q.push_back({s, s});
	bool lol = false;
	for (auto &n : nodes)
		n.mn = 1e9;
	for (auto &q : gmn)
		q = 1e9;
	for (int i = 0; i < n; i++)
	{
		if (seen[i] or i == p[i])
			continue;
		t.clear();
		sum += dfs(i);
		sort(t.begin(), t.end());
		q.push_back({t.front(), t.back()});
		auto [a, b] = q.back();
		for (int x : t)
			Q.push_back({{a, b}, x});
		for (int x : t)
			Q2.push_back({{b, a}, x});
		// for (int x : t)
		// 	upd(1, 0, n, x, a, b);
		// if (a <= s and s <= b)
		// 	lol = true;
	}
	sort(q.begin(), q.end());
	int st = 0;
	int lt = -1;
	int pl, pr;
	for (auto [a, b] : q)
	{
		if (lt == -1)
		{
			st = a;
			lt = b;
		}
		if (a > lt)
		{
			if (st <= s and s <= lt)
			{
				lol = true;
				pl = st, pr = lt;
			}
			sum += 2 * (a - lt);
			lt = b;
			st = a;
		}
		else
		{
			lt = max(lt, b);
		}
	}
	if (st <= s and s <= lt)
	{
		lol = true;
		pl = st, pr = lt;
	}
	if (pl == pr)
		lol = false;
	sort(Q.begin(), Q.end());
	sort(Q2.begin(), Q2.end(), greater<>());
	for (auto [p, i] : Q)
	{
		auto [a, b] = p;
		auto [x, y] = query(1, 0, n, a, b);
		upd(1, 0, n, i, min(x, a), y);
		gmn[i] = min(x, a);
	}
	for (auto [p, i] : Q2)
	{
		auto [b, a] = p;
		auto [x, y] = query(1, 0, n, a, b);
		upd(1, 0, n, i, x, max(y, b));
		gmx[i] = max(y, b);
	}
	// for (int p = 0; p < 21; p++)
	// {
	// 	for (int i = 0; i < n; i++)
	// 	{
	// 		auto [a, b] = query(1, 0, n, i, i);
	// 		auto [x, y] = query(1, 0, n, a, b);
	// 		// printf("%d %d %d\n", i, x, y);
	// 		upd(1, 0, n, i, x, y);
	// 	}
	// }
	int mn = 1e9;
	for (int i = 0; i < n; i++)
	{
		// auto [a, b] = query(1, 0, n, i, i);
		auto a = gmn[i], b = gmx[i];
		if (a <= pl and pr <= b)
			mn = min(mn, abs(i - s));
	}
#ifdef DEBUG
	printf("%d %d\n", lol, mn);
#endif
	if (lol)
		sum += 2 * mn;
	return sum;
}

Compilation message

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:127:2: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |  if (pl == pr)
      |  ^~
books.cpp:127:2: warning: 'pl' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	66764 KB	Output is correct
2	Correct	30 ms	66828 KB	Output is correct
3	Correct	30 ms	66744 KB	Output is correct
4	Correct	27 ms	66744 KB	Output is correct
5	Correct	28 ms	66836 KB	Output is correct
6	Correct	27 ms	66840 KB	Output is correct
7	Correct	27 ms	66772 KB	Output is correct
8	Correct	27 ms	66764 KB	Output is correct
9	Correct	27 ms	66756 KB	Output is correct
10	Correct	26 ms	66772 KB	Output is correct
11	Correct	26 ms	66784 KB	Output is correct
12	Correct	27 ms	66732 KB	Output is correct
13	Correct	26 ms	66832 KB	Output is correct
14	Correct	26 ms	66824 KB	Output is correct
15	Correct	28 ms	66772 KB	Output is correct
16	Correct	27 ms	66764 KB	Output is correct
17	Correct	26 ms	66748 KB	Output is correct
18	Correct	27 ms	66776 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	66764 KB	Output is correct
2	Correct	30 ms	66828 KB	Output is correct
3	Correct	30 ms	66744 KB	Output is correct
4	Correct	27 ms	66744 KB	Output is correct
5	Correct	28 ms	66836 KB	Output is correct
6	Correct	27 ms	66840 KB	Output is correct
7	Correct	27 ms	66772 KB	Output is correct
8	Correct	27 ms	66764 KB	Output is correct
9	Correct	27 ms	66756 KB	Output is correct
10	Correct	26 ms	66772 KB	Output is correct
11	Correct	26 ms	66784 KB	Output is correct
12	Correct	27 ms	66732 KB	Output is correct
13	Correct	26 ms	66832 KB	Output is correct
14	Correct	26 ms	66824 KB	Output is correct
15	Correct	28 ms	66772 KB	Output is correct
16	Correct	27 ms	66764 KB	Output is correct
17	Correct	26 ms	66748 KB	Output is correct
18	Correct	27 ms	66776 KB	Output is correct
19	Correct	29 ms	66904 KB	Output is correct
20	Correct	26 ms	66896 KB	Output is correct
21	Correct	31 ms	66772 KB	Output is correct
22	Correct	29 ms	66792 KB	Output is correct
23	Correct	28 ms	66872 KB	Output is correct
24	Correct	28 ms	66840 KB	Output is correct
25	Correct	27 ms	66848 KB	Output is correct
26	Correct	30 ms	66884 KB	Output is correct
27	Correct	29 ms	66880 KB	Output is correct
28	Correct	28 ms	66900 KB	Output is correct
29	Correct	27 ms	66784 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	66764 KB	Output is correct
2	Correct	30 ms	66828 KB	Output is correct
3	Correct	30 ms	66744 KB	Output is correct
4	Correct	27 ms	66744 KB	Output is correct
5	Correct	28 ms	66836 KB	Output is correct
6	Correct	27 ms	66840 KB	Output is correct
7	Correct	27 ms	66772 KB	Output is correct
8	Correct	27 ms	66764 KB	Output is correct
9	Correct	27 ms	66756 KB	Output is correct
10	Correct	26 ms	66772 KB	Output is correct
11	Correct	26 ms	66784 KB	Output is correct
12	Correct	27 ms	66732 KB	Output is correct
13	Correct	26 ms	66832 KB	Output is correct
14	Correct	26 ms	66824 KB	Output is correct
15	Correct	28 ms	66772 KB	Output is correct
16	Correct	27 ms	66764 KB	Output is correct
17	Correct	26 ms	66748 KB	Output is correct
18	Correct	27 ms	66776 KB	Output is correct
19	Correct	29 ms	66904 KB	Output is correct
20	Correct	26 ms	66896 KB	Output is correct
21	Correct	31 ms	66772 KB	Output is correct
22	Correct	29 ms	66792 KB	Output is correct
23	Correct	28 ms	66872 KB	Output is correct
24	Correct	28 ms	66840 KB	Output is correct
25	Correct	27 ms	66848 KB	Output is correct
26	Correct	30 ms	66884 KB	Output is correct
27	Correct	29 ms	66880 KB	Output is correct
28	Correct	28 ms	66900 KB	Output is correct
29	Correct	27 ms	66784 KB	Output is correct
30	Correct	1234 ms	146892 KB	Output is correct
31	Correct	1362 ms	126808 KB	Output is correct
32	Correct	132 ms	78472 KB	Output is correct
33	Correct	505 ms	98688 KB	Output is correct
34	Correct	511 ms	98764 KB	Output is correct
35	Correct	639 ms	102764 KB	Output is correct
36	Correct	824 ms	107820 KB	Output is correct
37	Correct	943 ms	107272 KB	Output is correct
38	Correct	988 ms	107508 KB	Output is correct
39	Correct	1026 ms	107496 KB	Output is correct
40	Correct	1088 ms	109256 KB	Output is correct
41	Correct	1120 ms	130152 KB	Output is correct
42	Correct	1184 ms	115052 KB	Output is correct
43	Correct	601 ms	99388 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	66860 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3590'
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	66764 KB	Output is correct
2	Correct	30 ms	66828 KB	Output is correct
3	Correct	30 ms	66744 KB	Output is correct
4	Correct	27 ms	66744 KB	Output is correct
5	Correct	28 ms	66836 KB	Output is correct
6	Correct	27 ms	66840 KB	Output is correct
7	Correct	27 ms	66772 KB	Output is correct
8	Correct	27 ms	66764 KB	Output is correct
9	Correct	27 ms	66756 KB	Output is correct
10	Correct	26 ms	66772 KB	Output is correct
11	Correct	26 ms	66784 KB	Output is correct
12	Correct	27 ms	66732 KB	Output is correct
13	Correct	26 ms	66832 KB	Output is correct
14	Correct	26 ms	66824 KB	Output is correct
15	Correct	28 ms	66772 KB	Output is correct
16	Correct	27 ms	66764 KB	Output is correct
17	Correct	26 ms	66748 KB	Output is correct
18	Correct	27 ms	66776 KB	Output is correct
19	Correct	29 ms	66904 KB	Output is correct
20	Correct	26 ms	66896 KB	Output is correct
21	Correct	31 ms	66772 KB	Output is correct
22	Correct	29 ms	66792 KB	Output is correct
23	Correct	28 ms	66872 KB	Output is correct
24	Correct	28 ms	66840 KB	Output is correct
25	Correct	27 ms	66848 KB	Output is correct
26	Correct	30 ms	66884 KB	Output is correct
27	Correct	29 ms	66880 KB	Output is correct
28	Correct	28 ms	66900 KB	Output is correct
29	Correct	27 ms	66784 KB	Output is correct
30	Correct	1234 ms	146892 KB	Output is correct
31	Correct	1362 ms	126808 KB	Output is correct
32	Correct	132 ms	78472 KB	Output is correct
33	Correct	505 ms	98688 KB	Output is correct
34	Correct	511 ms	98764 KB	Output is correct
35	Correct	639 ms	102764 KB	Output is correct
36	Correct	824 ms	107820 KB	Output is correct
37	Correct	943 ms	107272 KB	Output is correct
38	Correct	988 ms	107508 KB	Output is correct
39	Correct	1026 ms	107496 KB	Output is correct
40	Correct	1088 ms	109256 KB	Output is correct
41	Correct	1120 ms	130152 KB	Output is correct
42	Correct	1184 ms	115052 KB	Output is correct
43	Correct	601 ms	99388 KB	Output is correct
44	Incorrect	30 ms	66860 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3590'
45	Halted	0 ms	0 KB	-