Submission #1045839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045839		idas	Sky Walking (IOI19_walk)	C++17	0 / 100	75 ms	33968 KiB

walk

#include "walk.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N=1e5+10;
int n, m, id, hgt[N], gr[N];
ll dist[20*N];
vector<pii> ins[N];
vector<pii> ad[N];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int str, int g) {
	n=sz(x); m=sz(l);

	vector<pii> buildings;
	FOR(i, 0, n) {
		buildings.pb({h[i],i});
	}
	sort(buildings.begin(), buildings.end());
	reverse(buildings.begin(), buildings.end());

	set<pii> xs;
	FOR(i, 0, n) xs.insert({x[i],i});

	vector<pii> walks;
	FOR(i, 0, m) {
		walks.pb({y[i],i});
	}
	sort(walks.begin(), walks.end());

	id=n;
	for(auto[y, i] : walks) {
		while(!buildings.empty() && buildings.back().f<y) {
			int in=buildings.back().s;
			xs.erase({x[in],in});
			buildings.pop_back();
		}

		auto it=xs.lower_bound({x[l[i]],0});
		// assert((it->f)==x[l[i]]);

		int prv=-1, pos=0;
		while(true) {
			if(prv!=-1) {
				int w=(it->f)-pos;
				ad[prv].pb({id,w});
				ad[id].pb({prv,w});
			}

			prv=id; pos=it->f; hgt[id]=y; gr[id]=it->s;
			ins[it->s].pb({y,id++});

			if(it->s==r[i]) break;
			++it;
		}
	}

	FOR(i, 0, n) {
		hgt[i]=0; gr[i]=i;
		ins[i].pb({0,i});
		sort(ins[i].begin(), ins[i].end());
	}

	FOR(i, 0, 20*N) dist[i]=-1;

	queue<int> q;
	dist[str]=0; q.push(str);
	while(!q.empty()) {
		int id=q.front(); q.pop();

		int i=lower_bound(ins[gr[id]].begin(), ins[gr[id]].end(), pii{hgt[id],0})-ins[gr[id]].begin();

		// cout << id << " -> " << i << endl;

		if(i+1<ins[gr[id]].size()) {
			int upper=ins[gr[id]][i+1].s;
			if(dist[upper]==-1) {
				dist[upper]=dist[id]+(hgt[upper]-hgt[id]);
				q.push(upper);
			}
		}
		if(i-1>=0) {
			int lower=ins[gr[id]][i-1].s;
			if(dist[lower]==-1) {
				dist[lower]=dist[id]+(hgt[id]-hgt[lower]);
				q.push(lower);
			}
		}

		for(auto [idx, w] : ad[id]) {
			if(dist[idx]==-1) {
				dist[idx]=dist[id]+w;
				q.push(idx);
			}
		}
	}

	// FOR(i, 0, n) {
	// 	cout << "i: " << i << " " << dist[i] << '\n';
	// 	// for(auto it : ins[i]) {
	// 	// 	cout << it.f << " " << it.s << endl;
	// 	// }
	// }

	return dist[g];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:84:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   if(i+1<ins[gr[id]].size()) {
      |      ~~~^~~~~~~~~~~~~~~~~~~

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