oj.uz

Submission #590358

# Submission time Handle Problem Language Result Execution time Memory
590358 2022-07-05T21:27:53 Z Soumya1 Sky Walking (IOI19_walk) C++17
0 / 100
 182 ms 18368 KB 
#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = y.size();
	multiset<pair<int, long long>> st;
	vector<int> add[n], rem[n];
	for (int i = 0; i < m; i++) {
		add[l[i]].push_back(i);
		rem[r[i]].push_back(i);
	}
	vector<long long> ans(m);
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> nw;
		for (int j : add[i]) {
			if (i == 0) nw.push_back({y[j], y[j]}), ans[j] = y[j];
			else {
				long long v = 1e18;
				auto up = st.upper_bound({y[j], -5});
				if (up != st.end()) v = min(v, (*up).first - y[j] + (*up).second); 
				auto down = st.lower_bound({y[j], -5});
				if (!st.empty() && up == down && down != st.begin()) {
					down--;
				  v = min(v, y[j] - (*down).first + (*down).second); 
				}
				ans[j] = v;
				nw.push_back({y[j], ans[j]});
			}
		}
		for (auto x : nw) st.insert(x);
		for (int j : rem[i]) if (st.find({y[j], ans[j]}) != st.end()) st.erase(st.find({y[j], ans[j]}));
	}
	long long ret = 1e18;
	for (int i = 0; i < m; i++) {
		if (r[i] == n - 1) ret = min(ret, ans[i] + y[i] + x[n - 1] - x[0]);
	} 
	if (ret == 1e18) ret = -1;
	return ret;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3388 KB Output is correct
2 Correct 103 ms 4912 KB Output is correct
3 Correct 100 ms 5956 KB Output is correct
4 Correct 139 ms 13980 KB Output is correct
5 Correct 182 ms 18368 KB Output is correct
6 Correct 164 ms 16236 KB Output is correct
7 Correct 71 ms 10916 KB Output is correct
8 Incorrect 94 ms 15924 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3388 KB Output is correct
2 Correct 103 ms 4912 KB Output is correct
3 Correct 100 ms 5956 KB Output is correct
4 Correct 139 ms 13980 KB Output is correct
5 Correct 182 ms 18368 KB Output is correct
6 Correct 164 ms 16236 KB Output is correct
7 Correct 71 ms 10916 KB Output is correct
8 Incorrect 94 ms 15924 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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