oj.uz

Submission #388305

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

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

int n, m;

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

struct Event
{
	int x, t, id;
};

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;

	vector<Event> events;
	int cnt = 0;
	for(int x : l)
		events.push_back({x, 0, cnt++});
	cnt = 0;
	for(int x : r) {
		if(x != n-1)
			events.push_back({x, 1, cnt});
		++cnt;
	}
	sort(events.begin(), events.end(), [](Event a, Event b) {
		if(a.x != b.x) return a.x < b.x;
		return a.t < b.t;
	});
	mp[0] = 0;
	for(int i = 0, ptr = 0; i < n; i++) {
		for(; ptr < 2*m && events[ptr].x == i; ptr++) {
			int id = events[ptr].id;
			if(!events[ptr].t) {
				auto it = mp.lower_bound(y[id]);
				if(it != mp.end()) {
					bool ok = it->first != y[id];
					mp[y[id]] = it->second + abs(it->first - y[id]);
					if(ok) --it;
				}
				if(it != mp.begin()) {
					--it;
					if(!mp.count(y[id])) mp[y[id]] = inf;
					mp[y[id]] = min(mp[y[id]], it->second + abs(it->first - y[id]));
				}
				++qtd[y[id]];
			} else 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 0 ms 204 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

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