oj.uz

Submission #723919

# Submission time Handle Problem Language Result Execution time Memory
723919 2023-04-14T13:01:15 Z GrandTiger1729 Sky Walking (IOI19_walk) C++17
0 / 100
 190 ms 21568 KB 
#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
long long min_distance(vector<int> a, vector<int> h, vector<int> l, vector<int> r, vector<int> b, int s, int g){
	int n = a.size(), m = l.size();
	
	vector<vector<int>> ll(n), rr(n);
	for (int i = 0; i < m; i++){
		ll[l[i]].push_back(b[i]);
		rr[r[i]].push_back(b[i]);
	}
	map<int, long long> mp;
	for (int &j: ll[0])
		mp[j] = j;
	// cerr << "OK" << endl;
	for (int i = 1; i < n - 1; i++){
		set<int> vis;
		for (int &j: ll[i]){
			auto it = mp.lower_bound(j);
			if (it != mp.end()){
				if (it->first != j)
					mp[j] = it->second + it->first - j;
				else
					vis.insert(j);
			}
			if (mp.size() && it != mp.begin()){
				it--;
				mp[j] = min(mp[j], it->second + j - it->first);
			}
		}
		// cerr << "OK" << endl;
		for (int &j: rr[i]){
			if (vis.count(j))
				continue;
			auto it = mp.lower_bound(j);
			{
				auto it2 = it;
				it2++;
				if (it2 != mp.end())
					it2->second = min(it2->second, it->second + it2->first - j);
			}
			// cerr << "OKK" << endl;
			if (it != mp.begin()){
				auto it2 = it;
				it2--;
				it2->second = min(it2->second, it->second + j - it2->first);
			}
			mp.erase(it);
		}
		// cerr << i << ' ' << mp.size() << endl;
		// for (auto &it: mp)
		// 	cerr << it.first << ' ';
		// cerr << endl;
	}
	long long ans = INF;
	for (auto &it: mp){
		ans = min(ans, it.first + it.second);
	}
	ans += a[g] - a[s];
	return ans;
}

Subtask #1
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3660 KB Output is correct
2 Correct 99 ms 5880 KB Output is correct
3 Correct 100 ms 7260 KB Output is correct
4 Correct 152 ms 17224 KB Output is correct
5 Incorrect 190 ms 21568 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3660 KB Output is correct
2 Correct 99 ms 5880 KB Output is correct
3 Correct 100 ms 7260 KB Output is correct
4 Correct 152 ms 17224 KB Output is correct
5 Incorrect 190 ms 21568 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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