oj.uz

Submission #790650

# Submission time Handle Problem Language Result Execution time Memory
790650 2023-07-23T04:35:23 Z LittleCube Sky Walking (IOI19_walk) C++17
15 / 100
 118 ms 21648 KB 
#pragma GCC optimize("Ofast")
#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, M, K, S, T;
multiset<pll> st;
vector<int> in[100005], out[100005];

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	N = x.size(), M = l.size();
	for (int i = 0; i < M; i++)
	{
		in[l[i]].emplace_back(y[i]);
		if (r[i] < N - 1)
			out[r[i]].emplace_back(y[i]);
	}
	out[0].emplace_back(0);
	st.insert(pll(0, 0));
	for (int i = 0; i < N; i++)
	{
		for (int j : in[i])
		{
			ll dis = 1e18;
			auto iter = st.lower_bound(pll(j, 0));
			if (iter != st.end() && iter->F <= h[i])
				dis = min(dis, iter->S + abs(j - iter->F));
			if (iter != st.begin())
			{
				--iter;
				dis = min(dis, iter->S + abs(j - iter->F));
			}
			st.insert(pll(j, dis));
		}
		for (int j : out[i])
			st.erase(st.lower_bound(pll(j, 0)));
	}
	if(st.empty())
		return -1;
	ll ans = st.begin()->F + st.begin()->S + x[N - 1] - x[0];
	return (ans >= 1e18 ? -1 : ans);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7944 KB Output is correct
2 Correct 62 ms 10528 KB Output is correct
3 Correct 68 ms 11484 KB Output is correct
4 Correct 106 ms 17308 KB Output is correct
5 Correct 112 ms 21648 KB Output is correct
6 Correct 105 ms 19360 KB Output is correct
7 Correct 53 ms 13580 KB Output is correct
8 Correct 67 ms 19204 KB Output is correct
9 Correct 99 ms 20752 KB Output is correct
10 Correct 71 ms 18824 KB Output is correct
11 Correct 11 ms 6484 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7944 KB Output is correct
2 Correct 62 ms 10528 KB Output is correct
3 Correct 68 ms 11484 KB Output is correct
4 Correct 106 ms 17308 KB Output is correct
5 Correct 112 ms 21648 KB Output is correct
6 Correct 105 ms 19360 KB Output is correct
7 Correct 53 ms 13580 KB Output is correct
8 Correct 67 ms 19204 KB Output is correct
9 Correct 99 ms 20752 KB Output is correct
10 Correct 71 ms 18824 KB Output is correct
11 Correct 11 ms 6484 KB Output is correct
12 Correct 66 ms 11356 KB Output is correct
13 Correct 92 ms 17176 KB Output is correct
14 Correct 118 ms 21532 KB Output is correct
15 Correct 106 ms 17160 KB Output is correct
16 Correct 76 ms 17168 KB Output is correct
17 Correct 76 ms 17248 KB Output is correct
18 Correct 76 ms 17032 KB Output is correct
19 Correct 83 ms 17192 KB Output is correct
20 Correct 69 ms 13568 KB Output is correct
21 Incorrect 21 ms 8524 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5004 KB Output isn't correct
2 Halted 0 ms 0 KB -