oj.uz

Submission #1050151

# Submission time Handle Problem Language Result Execution time Memory
1050151 2024-08-09T07:44:39 Z Kel_Mahmut Sky Walking (IOI19_walk) C++17
0 / 100
 121 ms 15700 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

ll 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 = l.size();
	ll ans = LLONG_MAX;
	bool st3 = (s == 0) && (g == n - 1);
	for(int i = 0; i < n; i++)
		st3 &= h[i] == h[0];
	if(st3){
		set<pair<ll, ll>> act;
		vector<set<pair<ll, ll>>> skywalks(n);
		for(int i = 0; i < m; i++){
			skywalks[l[i]].insert(make_pair(y[i], 0));
		}
		for(int i = 0; i < m; i++){
			auto it = skywalks[r[i]].lower_bound(make_pair(y[i], -1));
			if(it != skywalks[r[i]].end() && it->first == y[i]){
				skywalks[r[i]].erase(it);
			}
			else{
				skywalks[r[i]].insert(make_pair(y[i], 1));
			}
		}

		for(auto [a, b] : skywalks[0]){
			act.insert({b, b});
		}

		for(int i = 0; i < n; i++){
			for(auto [a, b] : skywalks[i]){
				if(b == 0){
					ll minh = 1e16;
					auto it = act.lower_bound(make_pair(a, -1));
					if(it != act.end()){
						minh = min(minh, it->second + abs(a - it->first));
					}
					if(it != act.begin()){
						it = prev(it);
						minh = min(minh, it->second + abs(a - it->first));
					}
					act.insert(make_pair(a, minh));
				}
				else{
					auto it = act.lower_bound(make_pair(a, -1));
					ll cur = it->second;
					if(i == n - 1){
						ans = min(ans, cur + a);
					}
					assert(it->first == a);
					act.erase(it);
					it = act.lower_bound(make_pair(a, -1));
					if(it != act.end()){
						ll curheight = it->first;
						ll minh = min(it->second, cur + abs(it->first - a));
						act.erase(it);
						act.insert(make_pair(curheight, minh));
					}
					it = act.lower_bound(make_pair(a, -1));
					if(it != act.begin()){
						it = prev(it);
						ll curheight = it->first;
						ll minh = min(it->second, cur + abs(curheight - a));
						act.erase(it);
						act.insert(make_pair(curheight, minh));
					}
				}
			}
		}
		return ans + x[g] - x[s];
	}
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5212 KB Output is correct
2 Incorrect 121 ms 15700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5212 KB Output is correct
2 Incorrect 121 ms 15700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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