Submission #143102

#	Time	Username	Problem	Language	Result	Execution time	Memory
143102		model_code	Sky Walking (IOI19_walk)	Java	10 / 100	4143 ms	240708 KiB

walk

// 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 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43