oj.uz

Submission #388309

# Submission time Handle Problem Language Result Execution time Memory
388309 2021-04-10T21:19:00 Z LucaDantas Sky Walking (IOI19_walk) C++17
0 / 100
 27 ms 7252 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;
constexpr int maxn = 1e5+10;

int n, m;

map<long long, long long> mp, qtd;

vector<int> add[maxn], rmv[maxn];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, 
	vector<int> r, vector<int> y, int s, int g) {
	n = (int)h.size(); m = (int)l.size();
	// if(s != 0 || g != n-1) return 0;

	int cnt = 0;
	for(int x : l)
		add[x].push_back(cnt++);
	cnt = 0;
	for(int x : r) {
		if(x != n-1)
			rmv[x].push_back(cnt);
		++cnt;
	}
	mp[0] = 0;
	for(int i = 0; i < n; i++) {
		for(int id : add[i]) {
			++qtd[y[id]];
			if(mp.count(y[id])) continue;
			auto it = mp.lower_bound(y[id]);
			long long here = inf;
			if(it != mp.end()) here = it->second + abs(it->first - y[id]);
			if(it != mp.begin()) {
				--it;
				here = min(here, it->second + abs((it->first) - y[id]));
			}
			mp[y[id]] = here;
		}
		
		for(int id : rmv[i]) if(!(--qtd[y[id]])) mp.erase(y[id]);

		if(!i) mp.erase(0);
		if(!mp.size()) break;
	}
	if(!mp.size()) return -1;

	long long ans = inf;
	for(auto it : mp)
		ans = min(ans, it.second + it.first);
	return ans + x.back();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 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 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

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