oj.uz

Submission #427750

# Submission time Handle Problem Language Result Execution time Memory
427750 2021-06-14T21:19:47 Z albertolg101 Sky Walking (IOI19_walk) C++17
0 / 100
 27 ms 2592 KB 
#include <bits/stdc++.h>
#include "walk.h"

using namespace std; 
using ll = long long;
using pii = pair<int, int>;

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> L, std::vector<int> R, std::vector<int> y, int start, int end) {

	int n = x.size(), 
		m = y.size();

	vector<pii> l, r;

	for(int i = 0 ; i < m ; i++)
	{
		l.push_back({L[i], y[i]});
		r.push_back({R[i], y[i]});
	}

	sort(l.rbegin(), l.rend());
	sort(r.rbegin(), r.rend());

	ll ans = -1;

	multiset<ll> s;
	map<int, ll> dist;

	dist[0] = 0;
	s.insert(0);
	r.push_back({0, 0});

	for(int i = 0 ; i < n ; i++)
	{
		while(l.size() and l.back().first == i)
		{
			ll minDist = 1e18;
			auto pt = s.lower_bound(l.back().second);
			if(pt != s.end())
			{
				minDist = *pt - (ll)l.back().second + dist[*pt];
			}

			if(pt != s.begin())
			{
				pt = prev(pt);
				minDist = min(minDist, (ll)l.back().second - (*pt) + dist[*pt]);
			}

			s.insert(l.back().second);
			dist[l.back().second] = minDist;
			l.pop_back();
		}

		while(r.size() and r.back().first == i)
		{
			if(i == n - 1)
			{
				ll val = (ll)(x[n-1] - x[0]) + dist[r.back().second] + (ll)r.back().second;
				ans = (ans == -1 ? val : min(val, ans));
			}

			s.erase(r.back().second);
			r.pop_back();
		}
		/*
		cout << i << ": " ;
		for(auto i: s)
			cout << "{" << i << ", " << dist[i] << "} "; 
		cout << endl ;
		*/
		if(s.empty())
			break;
	}

	return ans;
}

Subtask #1
0 / 10.0

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

Subtask #5
0 / 43.0

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