oj.uz

Submission #455200

# Submission time Handle Problem Language Result Execution time Memory
455200 2021-08-05T16:50:48 Z blue Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 252832 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)
{
  l.push_back(s);
  r.push_back(s);
  y.push_back(0);
  
  l.push_back(g);
  r.push_back(g);
  y.push_back(0);
	// 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-2;
 
	int G_skywalk = M-1;
 
	// 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:442:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  442 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:465:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  465 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:494:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  494 |   for(int e = 0; e < edge[u].size(); e++)
      |                  ~~^~~~~~~~~~~~~~~~
walk.cpp:401:6: warning: unused variable 'P' [-Wunused-variable]
  401 |  int P = points.size();
      |      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 156816 KB Output is correct
2 Correct 75 ms 156780 KB Output is correct
3 Correct 75 ms 156864 KB Output is correct
4 Correct 75 ms 156824 KB Output is correct
5 Correct 76 ms 156872 KB Output is correct
6 Correct 76 ms 156856 KB Output is correct
7 Correct 75 ms 156868 KB Output is correct
8 Correct 75 ms 156776 KB Output is correct
9 Correct 75 ms 156740 KB Output is correct
10 Correct 78 ms 156768 KB Output is correct
11 Correct 75 ms 156808 KB Output is correct
12 Correct 78 ms 156824 KB Output is correct
13 Correct 76 ms 156964 KB Output is correct
14 Correct 91 ms 156784 KB Output is correct
15 Correct 77 ms 156740 KB Output is correct
16 Correct 75 ms 156864 KB Output is correct
17 Correct 76 ms 156768 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 156740 KB Output is correct
2 Correct 75 ms 156848 KB Output is correct
3 Correct 1738 ms 220172 KB Output is correct
4 Correct 1974 ms 245924 KB Output is correct
5 Incorrect 1245 ms 220136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 183008 KB Output is correct
2 Correct 3106 ms 247476 KB Output is correct
3 Correct 3676 ms 252832 KB Output is correct
4 Execution timed out 4074 ms 243644 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 183008 KB Output is correct
2 Correct 3106 ms 247476 KB Output is correct
3 Correct 3676 ms 252832 KB Output is correct
4 Execution timed out 4074 ms 243644 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 156816 KB Output is correct
2 Correct 75 ms 156780 KB Output is correct
3 Correct 75 ms 156864 KB Output is correct
4 Correct 75 ms 156824 KB Output is correct
5 Correct 76 ms 156872 KB Output is correct
6 Correct 76 ms 156856 KB Output is correct
7 Correct 75 ms 156868 KB Output is correct
8 Correct 75 ms 156776 KB Output is correct
9 Correct 75 ms 156740 KB Output is correct
10 Correct 78 ms 156768 KB Output is correct
11 Correct 75 ms 156808 KB Output is correct
12 Correct 78 ms 156824 KB Output is correct
13 Correct 76 ms 156964 KB Output is correct
14 Correct 91 ms 156784 KB Output is correct
15 Correct 77 ms 156740 KB Output is correct
16 Correct 75 ms 156864 KB Output is correct
17 Correct 76 ms 156768 KB Output is correct
18 Correct 76 ms 156740 KB Output is correct
19 Correct 75 ms 156848 KB Output is correct
20 Correct 1738 ms 220172 KB Output is correct
21 Correct 1974 ms 245924 KB Output is correct
22 Incorrect 1245 ms 220136 KB Output isn't correct
23 Halted 0 ms 0 KB -