Submission #1242379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242379		nvujica	Sky Walking (IOI19_walk)	C++20	0 / 100	16 ms	7240 KiB

walk

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#include "walk.h"

using namespace std;

const int maxn = 1e5 + 10;
const ll inf = (1LL << 60);

vector<int> poc[maxn];
vector <int> kraj[maxn];
set <pair<int, ll> > s;
set <pair<int, ll> > s2;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int g) {
	int n = x.size();
	int m = l.size();
	
	ll ans = x[n - 1] - x[0];

	for(int i = 0; i < m; i++){
		poc[l[i]].push_back(y[i]);
		kraj[r[i] + 1].push_back(y[i]);
	}

	for(int i = 0; i < poc[0].size(); i++){
		int vis = poc[0][i];
		
		s.insert({vis, vis});
	}

	for(int i = 1; i < n; i++){
		if(s.empty()) return -1;

		for(int j = 0; j < poc[i].size(); j++){
			int vis = poc[i][j];
			
			ll cost = inf;

			auto it = s.lower_bound({vis, 0});
			if(it != s.end()) cost = (*it).se + (*it).fi - vis;
			if(it != s.begin()){
				it--;
				cost = min(cost, (*it).se + vis - (*it).fi);
			}
			s.insert({vis, cost});
		}

		for(int j = 0; j < kraj[i].size(); j++){
			int vis = kraj[i][j];
			
			auto it = s.lower_bound({vis, 0});
			ll cost = (*it).se;

			it++;
			if(it != s.end()){
				ll c = cost + (*it).fi - vis;
				
				if(c < (*it).se){
					int vis2 = (*it).fi;
					s.erase(it);
					s.insert({vis2, c});
				}
				// (*it).se = min((*it).se, cost + (*it).fi - vis);
			}
			
			it = s.lower_bound({vis, 0});
			
			if(it != s.begin()){
				it--;
				ll c = cost + vis - (*it).fi;

				//(*it).se = min((*it).se, cost + vis - (*it).fi);
				if(c < (*it).se){
					int vis2 = (*it).fi;
					s.erase(it);
					s.insert({vis2, c});
				}
				
				it++;
			}


			s.erase({vis, cost});
		}
	}

	if(s.empty()) return -1;

	ll naj = inf;

	auto it = s.begin();

	while(it != s.end()){
		naj = min(naj, (*it).fi + (*it).se);
		it++;
	}

	return ans + naj;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43