oj.uz

Submission #455199

# Submission time Handle Problem Language Result Execution time Memory
455199 2021-08-05T16:46:52 Z blue Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 252720 KB 
#include "walk.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int N;
vector<int> X;
vector<int> H;

int M;
vector<int> L;
vector<int> R;
vector<int> Y;

int S;
int G;

const int INF = 1e9 + 1;
const int MX = 100'000;
const long long LONG_INF = 1'000'000'000'000'000'0LL;


int higher_skywalk(int w1, int w2)
{
	if(w1 == -1) return w2;
	else if(w2 == -1) return w1;
	else if(Y[w1] == Y[w2]) return max(w1, w2);
	else if(Y[w1] > Y[w2]) return w1;
	else return w2;
}

bool skywalk_leq(int w1, int w2)
{
	if(w1 == -1) return 1;
	if(w2 == -1)
	{
		return 0;
	}
	if(Y[w1] == Y[w2]) return w1 <= w2;
	return Y[w1] < Y[w2];
}

bool skywalk_less(int w1, int w2)
{
	if(w1 == -1 && w2 == -1) return 0;
	else if(w1 == -1 && w2 != -1) return 1;
	else if(w1 != -1 && w2 == -1) return 0;
	else
	{
		if(w1 == w2) return 0;
		if(Y[w1] == Y[w2]) return w1 < w2;
		return Y[w1] < Y[w2];
	}
}

struct point
{
	int b; //building
	int s; //skywalk
	int i;

	point()
	{
		;
	}

	point(int B, int S)
	{
		b = B;
		s = S;
	}

	point(int B, int S, int I)
	{
		b = B;
		s = S;
		i = I;
	}
};

bool operator < (point A, point B)
{
	if(A.b == B.b) return A.s < B.s;
	return A.b < B.b;
}

set<point> points;

struct walk_segtree
{
	int l;
	int r;
	vector<int> w;

	walk_segtree* left = NULL;
	walk_segtree* right = NULL;

	walk_segtree()
	{
		;
	}

	walk_segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) return;
		int m = (l+r)/2;
		left = new walk_segtree(l, m);
		right = new walk_segtree(m+1, r);
	}

	void add_skywalk(int W)
	{
		if(R[W] < l || r < L[W]) return;
		else if(L[W] <= l && r <= R[W])
		{
			w.push_back(W);
		}
		else
		{
			left->add_skywalk(W);
			right->add_skywalk(W);
		}
	}

	void sort_skywalks()
	{
		sort(w.begin(), w.end(), [] (int u, int v)
		{
			return Y[u] < Y[v];
		});

		if(left != NULL)
		{
			left->sort_skywalks();
			right->sort_skywalks();
		}
	}

	int locate_lower(int I, int W)
	{
		if(r < I || I < l) return -1;

		int ind = -1;
		for(int bit = 20; bit >= 0; bit--)
		{
			if(ind + (1 << bit) >= w.size()) continue;
			if(skywalk_leq(W, w[ind + (1 << bit)])) continue;
			ind += (1 << bit);
		}

		int curr_best = (ind == -1 ? -1 : w[ind]);

		if(left != NULL)
		{
			curr_best = higher_skywalk(curr_best, left->locate_lower(I, W));
			curr_best = higher_skywalk(curr_best, right->locate_lower(I, W));
		}

		return curr_best;
	}
};

int taller_building(int b1, int b2)
{
	if(b1 == -1) return b2;
	else if(b2 == -1) return b1;
	else if(H[b1] > H[b2]) return b1;
	else return b2;
}

struct build_segtree
{
	int l;
	int r;
	int h; //maximum height of a building

	build_segtree* left = NULL;
	build_segtree* right = NULL;

	build_segtree()
	{
		;
	}

	build_segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) h = H[L];
		else
		{
			int m = (l+r)/2;
			left = new build_segtree(l, m);
			right = new build_segtree(m+1, r);
			h = max(left->h, right->h);
		}
	}

	int rangemax(int L, int R)
	{
		if(R < L) return -INF;
		else if(R < l || r < L) return -INF;
		else if(L <= l && r <= R) return h;
		else return max(left->rangemax(L, R), right->rangemax(L, R));
	}
};






vector<int>* edge;
vector<long long>* dist;
vector<long long> src_dist(20'000'000, LONG_INF);

void add_edge(int u, int v, long long w)
{
	edge[u].push_back(v);
	dist[u].push_back(w);

	edge[v].push_back(u);
	dist[v].push_back(w);
	// cerr << u << ' ' << v << ' ' << w << '\n';

	assert(w >= 0);
}

struct pos
{
	int i;
};

bool operator < (pos A, pos B)
{
	if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
	return src_dist[A.i] < src_dist[B.i];
}





long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	// cerr << "A\n";
	N = x.size();
	X = x;
	H = h;

	M = l.size();
	L = l;
	R = r;
	Y = y;

	S = s;
	G = g;

	walk_segtree S_W(0, N-1);
	for(int j = 0; j < M; j++)
		S_W.add_skywalk(j);

	S_W.sort_skywalks();

	// cerr << "B\n";


	for(int j = 0; j < M; j++)
	{
		int LL = S_W.locate_lower(L[j], j);
		if(LL != -1)
			points.insert(point(L[j], LL));

		int RL = S_W.locate_lower(R[j], j);
		if(RL != -1)
			points.insert(point(R[j], RL));
	}

	// cerr << "C\n";



	for(int j = 0; j < M; j++)
	{
		if(L[j] <= S && S <= R[j] && Y[j] <= H[S])
		{
			points.insert(point(S, j));
		}

		if(L[j] <= G && G <= R[j] && Y[j] <= H[G])
			points.insert(point(G, j));
	}

	// cerr << "D\n";




	build_segtree S_B(0, N-1);

	// cerr << "E\n";



	int S_skywalk = M;
	L.push_back(S);
	R.push_back(S);
	Y.push_back(0);

	int G_skywalk = M+1;
	L.push_back(G);
	R.push_back(G);
	Y.push_back(0);

	// cerr << "F\n";





	for(int j = 0; j < M; j++)
	{
		// cerr << "j = " << j << '\n';
		for(int PT: vector<int>{S, G})
		{
			// S_B.rangemax(L[j], min(R[j], PT));
			// cerr << "query done\n";
			if(L[j] <= PT && S_B.rangemax(L[j], min(R[j], PT)) >= Y[j])
			{
				// cerr << "entered if statement\n";
				int lo = L[j];
				int hi = min(R[j], PT);
				int mid;
				// cerr << "check\n";
				while(lo != hi)
				{
					mid = (lo+hi)/2 + 1;
					// cerr << lo << ' ' << hi << ' ' << mid << '\n';
					if(S_B.rangemax(mid, hi) >= Y[j])
						lo = mid;
					else
						hi = mid-1;
				}
				// cerr << lo << ' ' << hi << '\n';
				mid = lo;

				if(H[mid] >= Y[j])
				{
					int tmp = S_W.locate_lower(mid, j);
					if(tmp != -1)
					{
						points.insert(point(mid, j));
						points.insert(point(mid, tmp));
					}
				}
			}
			// else cerr << "not entered\n";

			// cerr << "left done\n";



			if(PT <= R[j] && S_B.rangemax(max(L[j], PT), R[j]) >= Y[j])
			{
				int lo = max(L[j], PT);
				int hi = R[j];
				int mid;
				while(lo != hi)
				{
					mid = (lo+hi)/2;
					if(S_B.rangemax(lo, mid) >= Y[j])
						hi = mid;
					else
						lo = mid+1;
				}
				mid = lo;

				if(H[mid] >= Y[j])
				{
					int tmp = S_W.locate_lower(mid, j);
					if(tmp != -1)
					{
						points.insert(point(mid, j));
						points.insert(point(mid, tmp));
					}
				}
			}
		}
	}


	// cerr << "G\n";


	int P = points.size();
	vector<point> points_vector;
	int ct = 0;
	while(!points.empty())
	{
		point pt = *points.begin();
		points.erase(points.begin());
		ct++;
		pt.i = ct-1;
		points_vector.push_back(pt);
	}

	// cerr << "H\n";

	ct++;
	points_vector.push_back(point(S, S_skywalk, ct-1));
	int S_vertex = ct-1;

	ct++;
	points_vector.push_back(point(G, G_skywalk, ct-1));
	int G_vertex = ct-1;




	// for(point pt: points_vector) cerr << X[pt.b] << ' ' << Y[pt.s] << '\n';

	// cerr << "check\n";

	// cerr << "I\n";


	edge = new vector<int>[ct];
	dist = new vector<long long>[ct];

	sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
	{
		if(p1.b == p2.b) return (skywalk_less(p1.s, p2.s));
		return p1.b < p2.b;
	});

	for(int z = 0; z+1 < points_vector.size(); z++)
	{
		point p1 = points_vector[z];
		point p2 = points_vector[z+1];
		if(p1.b == p2.b)
		{
			add_edge(p1.i, p2.i, Y[p2.s] - Y[p1.s]);
			// cerr << p1.b << ' ' << p1.s << "    " << p2.b << ' ' << p2.s << '\n';
			// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << Y[p2.s] - Y[p1.s] << '\n';
		}
	}






	sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
	{
		if(p1.s == p2.s) return p1.b < p2.b;
		return skywalk_less(p1.s, p2.s);
	});

	for(int z = 0; z+1 < points_vector.size(); z++)
	{
		point p1 = points_vector[z];
		point p2 = points_vector[z+1];
		if(p1.s == p2.s)
		{
			add_edge(p1.i, p2.i, X[p2.b] - X[p1.b]);
			// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << X[p2.b] - X[p1.b] << '\n';
		}
	}

	// cerr << "Q\n";

	// if(N+M > 200)
	// {
	// 	while(1);
	// }


	src_dist[S_vertex] = 0;
	set<pos> tbv;
	for(int i = 0; i < ct; i++) tbv.insert(pos{i});
	while(!tbv.empty())
	{
		int u = tbv.begin()->i;
		tbv.erase(tbv.begin());
		// cerr << "u = " << u << '\n';
		// cerr << src_dist[u] << '\n';

		for(int e = 0; e < edge[u].size(); e++)
		{
			int v = edge[u][e];
			long long w = dist[u][e];

			if(src_dist[v] > src_dist[u] + w)
			{
				tbv.erase(pos{v});
				src_dist[v] = src_dist[u] + w;
				// cerr << "w = " << w << '\n';
				tbv.insert(pos{v});
			}
		}
	}
	// cerr << "Z\n";

	long long ans = src_dist[G_vertex];
	if(ans >= LONG_INF)
		ans = -1;




	return ans;
}

Compilation message

walk.cpp: In member function 'int walk_segtree::locate_lower(int, int)':
walk.cpp:151:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    if(ind + (1 << bit) >= w.size()) continue;
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
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:441:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  441 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:464:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  464 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:493:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  493 |   for(int e = 0; e < edge[u].size(); e++)
      |                  ~~^~~~~~~~~~~~~~~~
walk.cpp:400:6: warning: unused variable 'P' [-Wunused-variable]
  400 |  int P = points.size();
      |      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 156740 KB Output is correct
2 Correct 83 ms 156748 KB Output is correct
3 Correct 76 ms 156868 KB Output is correct
4 Correct 78 ms 156740 KB Output is correct
5 Correct 79 ms 156828 KB Output is correct
6 Correct 89 ms 156808 KB Output is correct
7 Correct 77 ms 156868 KB Output is correct
8 Correct 85 ms 156764 KB Output is correct
9 Correct 77 ms 156764 KB Output is correct
10 Correct 77 ms 156864 KB Output is correct
11 Correct 77 ms 156792 KB Output is correct
12 Correct 78 ms 156840 KB Output is correct
13 Correct 78 ms 156740 KB Output is correct
14 Correct 80 ms 156868 KB Output is correct
15 Correct 78 ms 156784 KB Output is correct
16 Correct 79 ms 156876 KB Output is correct
17 Correct 90 ms 156816 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 156844 KB Output is correct
2 Correct 78 ms 156740 KB Output is correct
3 Correct 1847 ms 220344 KB Output is correct
4 Correct 2133 ms 245752 KB Output is correct
5 Incorrect 1279 ms 220120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 182968 KB Output is correct
2 Correct 3123 ms 247612 KB Output is correct
3 Correct 3744 ms 252720 KB Output is correct
4 Execution timed out 4109 ms 242612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 182968 KB Output is correct
2 Correct 3123 ms 247612 KB Output is correct
3 Correct 3744 ms 252720 KB Output is correct
4 Execution timed out 4109 ms 242612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 156740 KB Output is correct
2 Correct 83 ms 156748 KB Output is correct
3 Correct 76 ms 156868 KB Output is correct
4 Correct 78 ms 156740 KB Output is correct
5 Correct 79 ms 156828 KB Output is correct
6 Correct 89 ms 156808 KB Output is correct
7 Correct 77 ms 156868 KB Output is correct
8 Correct 85 ms 156764 KB Output is correct
9 Correct 77 ms 156764 KB Output is correct
10 Correct 77 ms 156864 KB Output is correct
11 Correct 77 ms 156792 KB Output is correct
12 Correct 78 ms 156840 KB Output is correct
13 Correct 78 ms 156740 KB Output is correct
14 Correct 80 ms 156868 KB Output is correct
15 Correct 78 ms 156784 KB Output is correct
16 Correct 79 ms 156876 KB Output is correct
17 Correct 90 ms 156816 KB Output is correct
18 Correct 79 ms 156844 KB Output is correct
19 Correct 78 ms 156740 KB Output is correct
20 Correct 1847 ms 220344 KB Output is correct
21 Correct 2133 ms 245752 KB Output is correct
22 Incorrect 1279 ms 220120 KB Output isn't correct
23 Halted 0 ms 0 KB -