Submission #1344050

#TimeUsernameProblemLanguageResultExecution timeMemory
1344050Jawad_Akbar_JJSky Walking (IOI19_walk)C++20
Compilation error
0 ms0 KiB
#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;
const int N = 1<<17;
int Nxt[N][20], cur;
long long Mn[9<<17];
set<pair<int, int>> st[N];
vector<pair<int, int>> nei[N];
vector<int> v;

int Find(int i, int j){
	// cout<<"here "<<endl;
	auto u = st[i].upper_bound({j, -1});
	int vl;
	if (u == st[i].end() or (*u).first > j){
		vl = ++cur;
		st[i].insert({j, vl});
	}
	// cout<<"done"<<endl;
	return vl;
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int t){
	int n = x.size(), m = l.size();
	
	h.push_back(1000000005);
	for (int i=0;i<=n;i++){
		while (v.size() > 0 and h[v.back()] < h[i])
			Nxt[v.back()][0] = i, v.pop_back();
		v.push_back(i), Nxt[i][0] = n;
	}
	Nxt[n][0] = cur = n;

	for (int i=0;i<n;i++)
		// cout<<Nxt[i][0]<<' ';
	// cout<<endl;

	for (int j=0;j<18;j++){
		for (int i=0;i<=n;i++)
			Nxt[i][j+1] = Nxt[Nxt[i][j]][j];
	}


	for (int i=0;i<m;i++){
		int f = Find(l[i], y[i]);
		// cout<<i<<endl;
		// cout<<" :: ";
		while (l[i] != r[i]){
			int nx = l[i] + 1;
			for (int j=18;j+1;j--){
				if (h[Nxt[nx][j]] < y[i])
					nx = Nxt[nx][j];
			}
			if (h[nx] < y[i])
				nx = Nxt[nx][0];
			// cout<<nx<<' ';
			int F = Find(nx, y[i]);

			nei[f].push_back({F, x[nx] - x[l[i]]});
			nei[F].push_back({f, x[nx] - x[l[i]]});
			l[i] = nx, f = F;
		}
		// cout<<endl;
	}
	// return 0;

	for (int i=0;i<n;i++){
		int lst = i + 1, Hei = 0;
		for (auto [hei, j] : st[i]){
			nei[lst].push_back({j, hei - Hei});
			nei[j].push_back({lst, hei - Hei});
			Hei = hei;
			lst = j;
		}
	}
	// return 0;

	for (int i=1;i<=cur;i++)
		Mn[i] = 1e15 * (i != s + 1);
	priority_queue<pair<long long, int>> pq;
	pq.push({0, s + 1});

	while (pq.size() > 0){
		auto [mn, u] = pq.top();
		pq.pop();

		mn = -mn;
		if (mn != Mn[u])
			continue;

		for (auto [i, w] : nei[u]){
			if (Mn[i] > Mn[u] + w){
				Mn[i] = Mn[u] + w;
				pq.push({-Mn[i], i});
			}
		}
	}

	if (Mn[t + 1] == 1e15)
		return -1;
	return Mn[t + 1];
}

int main() {
	int n, m;
	cin>>n>>m;
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		cin>>x[i]>>h[i];

	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		cin>>l[i]>>r[i]>>y[i];

	int s, g;
	cin>>s>>g;

	long long result = min_distance(x, h, l, r, y, s, g);
	cout<<result<<endl;
	
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccTw97K7.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchZm2Ty.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status