oj.uz

Submission #1050184

# Submission time Handle Problem Language Result Execution time Memory
1050184 2024-08-09T07:53:42 Z Kel_Mahmut Sky Walking (IOI19_walk) C++14
0 / 100
 187 ms 31804 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({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 [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;
}

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 [a, b] : skywalks[0]){
      |            ^
walk.cpp:41:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |    for(auto [a, b] : 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 14 ms 5192 KB Output is correct
2 Correct 157 ms 15700 KB Output is correct
3 Correct 120 ms 18256 KB Output is correct
4 Correct 162 ms 25936 KB Output is correct
5 Correct 187 ms 31804 KB Output is correct
6 Correct 158 ms 28332 KB Output is correct
7 Correct 53 ms 17328 KB Output is correct
8 Incorrect 86 ms 25388 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5192 KB Output is correct
2 Correct 157 ms 15700 KB Output is correct
3 Correct 120 ms 18256 KB Output is correct
4 Correct 162 ms 25936 KB Output is correct
5 Correct 187 ms 31804 KB Output is correct
6 Correct 158 ms 28332 KB Output is correct
7 Correct 53 ms 17328 KB Output is correct
8 Incorrect 86 ms 25388 KB Output isn't correct
9 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 -