oj.uz

Submission #143102

# Submission time Handle Problem Language Result Execution time Memory
143102 2019-08-13T01:29:41 Z model_code Sky Walking (IOI19_walk) Java 11
10 / 100
 4000 ms 240708 KB 
// correct/akm-full.java
import java.util.*;

class walk {

	public static final int MAXN = 200 * 1000 + 10;
	public static final int MAXM = 200 * 1000 + 10;
	public static final int MAXRM = 5 * MAXM;
	public static final int MAXV = 2 * 2 * MAXRM;
	public static final long INF = 1000l * 1000 * 1000 * 1000 * 1000 * 1000;

	class pair implements Comparable<pair>{
		public long a, b;
		public pair(long a, long b){
			this.a = a;
			this.b = b;
		}

		@Override
			public int compareTo(pair cur){
				if(this.a < cur.a)return -1;
				if(this.a > cur.a)return 1;
				if(this.b < cur.b)return -1;
				if(this.b > cur.b)return 1;
				return 0;
			}
		@Override
			public boolean equals(Object o){
				if (o == this) {
					return true;
				}
				if (!(o instanceof pair)) {
					return false;
				}
				pair cur = (pair) o;
				return (this.a == cur.a && this.b == cur.b);
			}
		@Override
			public int hashCode() {
				int p = 1000000007;
				return p * (int)this.a + (int)this.b;
			}
	}

	public long[] dist = new long[MAXV];
	public int vcnt = 0;
	public ArrayList<ArrayList<pair>> edges = new ArrayList<>();
 	public TreeSet<pair> dij = new TreeSet<>();
	public int[] last_x = new int[MAXRM];
	public int[] last_vertex = new int[MAXRM];
	public int[] last_height = new int[MAXN];
	public int[] first_height = new int[MAXN];
	public ArrayList<ArrayList<pair>> adds = new ArrayList<>();
	public ArrayList<ArrayList<pair>> removes = new ArrayList<>();
	public TreeSet<pair> walks = new TreeSet<pair>();

	long dijkstra(int start, int dest)
	{
		for (int i = 0; i < vcnt; i++)
			dist[i] = INF;
		dist[start] = 0;
		dij.add(new pair(dist[start], start));
		while (!dij.isEmpty())
		{
			int v =	(int)dij.pollFirst().b;
			if (v == dest)
				return dist[v];
			for (int i = 0; i < edges.get(v).size(); i++)
			{
				int u = (int)edges.get(v).get(i).a;
				int w = (int)edges.get(v).get(i).b;
				if (dist[u] > dist[v] + w)
				{
					dij.remove(new pair(dist[u], u));
					dist[u] = dist[v] + w;
					dij.add(new pair(dist[u], u));
				}
			}
		}
		return -1;
	}

	void add_edge(int u, int v, int w)
	{
		edges.get(u).add(new pair(v, w));
		edges.get(v).add(new pair(u, w));
	}

	int make_vertex(int walk, int x)
	{
		if (last_x[walk] == x)
			return last_vertex[walk];
		int cur = vcnt++;
		edges.add(new ArrayList<>());
		if (last_vertex[walk] != -1)
			add_edge(last_vertex[walk], cur, x - last_x[walk]);
		last_x[walk] = x;
		last_vertex[walk] = cur;
		return cur;
	}

	void break_segments(ArrayList<Integer> l, ArrayList<Integer> r, ArrayList<Integer> y, int s, int[] h)
	{
		TreeSet<Integer> ts = new TreeSet<Integer>();
		for (int i = 0; i < h.length; i++)
			ts.add(h[i]);
		List<Integer> heights = new ArrayList<Integer>();
		for (Integer x: ts)
			heights.add(x);
		for (int i = 0; i < heights.size(); i++)
		{
			last_height[i] = -1;
			first_height[i] = h.length + 1;
		}
		for (int i = 0; i < h.length; i++)
		{
			int idx = Collections.binarySearch(heights, h[i]);
			if (i <= s)
				last_height[idx] = Math.max(last_height[idx], i);
			if (i >= s)
				first_height[idx] = Math.min(first_height[idx], i);
		}
		for (int i = heights.size() - 2; i >= 0; i--)
		{
			last_height[i] = Math.max(last_height[i], last_height[i + 1]);
			first_height[i] = Math.min(first_height[i], first_height[i + 1]);
		}
		for (int i = 0; i < l.size(); i++)
			if (l.get(i) < s && r.get(i) > s)
			{
				int idx = Collections.binarySearch(heights, y.get(i));
				if (idx < 0)
					idx = -(idx + 1);
				int x = l.get(i);
				int a = last_height[idx];
				int b = first_height[idx];
				int q = r.get(i);

				if (x < a)
				{
					r.set(i, a);
					if (a < b)
					{
						l.add(a);
						r.add(b);
						y.add(y.get(i));
					}
				}
				else
				{
					r.set(i, b);
				}
				if (q > b)
				{
					l.add(b);
					r.add(q);
					y.add(y.get(i));
				}
				else
				{
				}
			}
	}

	long min_distance(int[] x, int[] h, int[] orig_l, int[] orig_r, int[] orig_y, int s, int g)
	{
		if (s == g)
			return 0;
		int n = x.length;

		ArrayList<Integer> l = new ArrayList<Integer>();
		for (int ttt: orig_l)
			l.add(ttt);
		ArrayList<Integer> r = new ArrayList<Integer>();
		for (int ttt: orig_r)
			r.add(ttt);
		ArrayList<Integer> y = new ArrayList<Integer>();
		for (int ttt: orig_y)
			y.add(ttt);
		for (int i = 0; i < n; i++)
		{
			adds.add(new ArrayList<>());
			removes.add(new ArrayList<>());
		}
		break_segments(l, r, y, s, h);
		break_segments(l, r, y, g, h);
		int m = l.size();

		for (int i = 0; i < m; i++)
		{
			last_x[i] = last_vertex[i] = -1;
			adds.get(l.get(i)).add(new pair(y.get(i), i));
			removes.get(r.get(i)).add(new pair(y.get(i), i));
		}
		int sv = -1, gv = -1;
		long res = 0;
		walks = new TreeSet<>();
		for (int i = 0; i < n; i++)
		{
			Collections.sort(adds.get(i));
			for (int j = 0; j < adds.get(i).size(); j++)
			{
				int v = make_vertex((int)adds.get(i).get(j).b, x[i]);
				pair it = walks.lower(adds.get(i).get(j));
				if (it != null)
				{
					int u = make_vertex((int)it.b, x[i]);
					add_edge(u, v, (int)(adds.get(i).get(j).a - it.a));
				}
				walks.add(adds.get(i).get(j));
			}
			if (i == s)
			{
				if (walks.isEmpty() || walks.first().a > h[i])
					return -1;
				sv = make_vertex((int)walks.first().b, x[i]);
				res += walks.first().a;
			}
			if (i == g)
			{
				if (walks.isEmpty() || walks.first().a > h[i])
					return -1;
				gv = make_vertex((int)walks.first().b, x[i]);
				res += walks.first().a;
			}
			Collections.sort(removes.get(i));
			Collections.reverse(removes.get(i));
			for (int j = 0; j < removes.get(i).size(); j++)
			{
				int v = make_vertex((int)removes.get(i).get(j).b, x[i]);
				pair it = walks.lower(removes.get(i).get(j));
				if (it != null)
				{
					int u = make_vertex((int)it.b, x[i]);
					add_edge(u, v, (int)(removes.get(i).get(j).a - it.a));
				}
				walks.remove(removes.get(i).get(j));
			}
		}
		long dij_res = dijkstra(sv, gv);
		if(dij_res == -1)
			return -1;
		return res + dij_res;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 73100 KB Output is correct
2 Correct 191 ms 73032 KB Output is correct
3 Correct 192 ms 72648 KB Output is correct
4 Correct 203 ms 73032 KB Output is correct
5 Correct 212 ms 73028 KB Output is correct
6 Correct 279 ms 73036 KB Output is correct
7 Correct 214 ms 72772 KB Output is correct
8 Correct 265 ms 72928 KB Output is correct
9 Correct 270 ms 73048 KB Output is correct
10 Correct 227 ms 73404 KB Output is correct
11 Correct 211 ms 72936 KB Output is correct
12 Correct 211 ms 72860 KB Output is correct
13 Correct 216 ms 73156 KB Output is correct
14 Correct 240 ms 72984 KB Output is correct
15 Correct 232 ms 72844 KB Output is correct
16 Correct 239 ms 72936 KB Output is correct
17 Correct 214 ms 72824 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 73292 KB Output is correct
2 Correct 227 ms 73044 KB Output is correct
3 Correct 2643 ms 165420 KB Output is correct
4 Execution timed out 4043 ms 240092 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 114080 KB Output is correct
2 Correct 2897 ms 181052 KB Output is correct
3 Correct 3583 ms 236104 KB Output is correct
4 Execution timed out 4143 ms 240708 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 114080 KB Output is correct
2 Correct 2897 ms 181052 KB Output is correct
3 Correct 3583 ms 236104 KB Output is correct
4 Execution timed out 4143 ms 240708 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 73100 KB Output is correct
2 Correct 191 ms 73032 KB Output is correct
3 Correct 192 ms 72648 KB Output is correct
4 Correct 203 ms 73032 KB Output is correct
5 Correct 212 ms 73028 KB Output is correct
6 Correct 279 ms 73036 KB Output is correct
7 Correct 214 ms 72772 KB Output is correct
8 Correct 265 ms 72928 KB Output is correct
9 Correct 270 ms 73048 KB Output is correct
10 Correct 227 ms 73404 KB Output is correct
11 Correct 211 ms 72936 KB Output is correct
12 Correct 211 ms 72860 KB Output is correct
13 Correct 216 ms 73156 KB Output is correct
14 Correct 240 ms 72984 KB Output is correct
15 Correct 232 ms 72844 KB Output is correct
16 Correct 239 ms 72936 KB Output is correct
17 Correct 214 ms 72824 KB Output is correct
18 Correct 246 ms 73292 KB Output is correct
19 Correct 227 ms 73044 KB Output is correct
20 Correct 2643 ms 165420 KB Output is correct
21 Execution timed out 4043 ms 240092 KB Time limit exceeded
22 Halted 0 ms 0 KB -