oj.uz

Submission #1050216

# Submission time Handle Problem Language Result Execution time Memory
1050216 2024-08-09T08:02:18 Z Kel_Mahmut Sky Walking (IOI19_walk) C++14
0 / 100
 143 ms 28752 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(0, y[i]));
		}
		for(int i = 0; i < m; i++){
			auto it = skywalks[r[i]].lower_bound(make_pair(0, y[i]));
			if(it != skywalks[r[i]].end() && it->second == y[i] && it->first == 0){
				skywalks[r[i]].erase(it);
			}
			else{
				skywalks[r[i]].insert(make_pair(1, y[i]));
			}
		}

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

		for(int i = 0; i < n; i++){
			// cout << "BUILDING: " << i << endl;
			// for(auto [a, b] : act){
			// 	cout << "HEIGHT: " << a  << " COST: " << b << endl;
			// }
			for(auto [b, a] : 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;
}

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |   for(auto [b, a] : skywalks[0]){
      |            ^
walk.cpp:41:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |    for(auto [b, a] : skywalks[i]){
      |             ^

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 Correct 129 ms 15504 KB Output is correct
3 Correct 135 ms 16252 KB Output is correct
4 Correct 121 ms 21688 KB Output is correct
5 Correct 143 ms 27736 KB Output is correct
6 Correct 131 ms 24256 KB Output is correct
7 Correct 50 ms 14164 KB Output is correct
8 Correct 56 ms 21328 KB Output is correct
9 Correct 122 ms 28752 KB Output is correct
10 Correct 95 ms 27984 KB Output is correct
11 Incorrect 7 ms 4188 KB Output isn't correct
12 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 Correct 129 ms 15504 KB Output is correct
3 Correct 135 ms 16252 KB Output is correct
4 Correct 121 ms 21688 KB Output is correct
5 Correct 143 ms 27736 KB Output is correct
6 Correct 131 ms 24256 KB Output is correct
7 Correct 50 ms 14164 KB Output is correct
8 Correct 56 ms 21328 KB Output is correct
9 Correct 122 ms 28752 KB Output is correct
10 Correct 95 ms 27984 KB Output is correct
11 Incorrect 7 ms 4188 KB Output isn't correct
12 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 -