Submission #143184

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143184	2019-08-13T09:49:26 Z	mmaxio	Sky Walking (IOI19_walk)	Java 11	10 / 100	4000 ms	234640 KB

walk

import java.io.*;
import java.util.*;

public class walk {

	static class Point {
		int x, y;

		int id;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		boolean sameAs(Point o) {
			return x == o.x && y == o.y;
		}

		@Override
		public String toString() {
			return "(" + x + ", " + y + ")";
		}
	}

	static class Segment implements Comparable<Segment> {
		Point p, q;

		public Segment(Point p, Point q) {
			this.p = p;
			this.q = q;
		}

		@Override
		public int compareTo(Segment o) {
			return Integer.compare(p.x, o.p.x);
		}

		@Override
		public String toString() {
			if (p.x == q.x) {
				return String.format("vert at x = %s, y = %s..%s", p.x, p.y,
						q.y);
			} else {
				return String
						.format("hor at y = %s, x = %s..%s", p.y, p.x, q.x);
			}
		}

		boolean contains(Point pt) {
			return p.x <= pt.x && pt.x <= q.x && p.y <= pt.y && pt.y <= q.y;
		}
	}

	static class Event implements Comparable<Event> {

		int y;
		/**
		 * 0 - horizontal 1 - end of vertical 2 - start of vertical
		 */
		int type;

		Segment seg;

		public Event(int y, int type, Segment seg) {
			this.y = y;
			this.type = type;
			this.seg = seg;
		}

		@Override
		public int compareTo(Event o) {
			if (y != o.y) {
				return y < o.y ? -1 : 1;
			}
			return Integer.compare(type, o.type);
		}
	}

	static final int MAX_POINTS = 6_000_000;
	static final long INF = Long.MAX_VALUE / 5;
	Point[] lst = new Point[MAX_POINTS];
	int lstSz = 0;

	Point[] horEnds;
	int horEndsSz = 0;
	Point[] verEnds;
	int verEndsSz = 0;

	Random rng = new Random();

	long solve(int[] x1s, int[] y1s, int[] x2s, int[] y2s, int fromX, int fromY, int toX, int toY) {

		int n = x1s.length;
		// int n = 20000;

		Segment[] a = new Segment[n];

		int[] allX = new int[2 * n];

		horEnds = new Point[2 * n];
		verEnds = new Point[2 * n];

		Event[] verEvs = new Event[2 * n];
		int verEvsSz = 0;
		Event[] horEvs = new Event[n];
		int horEvsSz = 0;

		for (int i = 0; i < n; i++) {
			int x1 = x1s[i];
			int y1 = y1s[i];
			int x2 = x2s[i];
			int y2 = y2s[i];

			// int x1, y1, x2, y2;
			// if (i < n / 2) {
			// x1 = i;
			// y1 = 0;
			// x2 = i;
			// y2 = n / 2 - 1;
			// } else {
			// x1 = 0;
			// y1 = i - n / 2;
			// x2 = n / 2 - 1;
			// y2 = i - n / 2;
			// }

			// int x1, y1, x2, y2;
			// if (rng.nextBoolean()) {
			// x1 = x2 = rng.nextInt(1_000_000_000);
			// y1 = rng.nextInt(1_000_000_000);
			// y2 = rng.nextInt(1_000_000_000);
			// } else {
			// y1 = y2 = rng.nextInt(1_000_000_000);
			// x1 = rng.nextInt(1_000_000_000);
			// x2 = rng.nextInt(1_000_000_000);
			// }

			allX[2 * i] = x1;
			allX[2 * i + 1] = x2;

			Point p = new Point(x1, y1);
			Point q = new Point(x2, y2);

      // System.out.println(p + " -- " + q);

			// System.err.println(p + " - " + q);

			lst[lstSz++] = p;
			lst[lstSz++] = q;

			if (p.x + p.y > q.x + q.y) {
				Point tmp = p;
				p = q;
				q = tmp;
			}

			a[i] = new Segment(p, q);

			if (p.x == q.x) {
				verEvs[verEvsSz++] = new Event(q.y, 2, a[i]);
				verEvs[verEvsSz++] = new Event(p.y, 1, a[i]);

				verEnds[verEndsSz++] = p;
				verEnds[verEndsSz++] = q;
			} else {
				horEvs[horEvsSz++] = new Event(p.y, 0, a[i]);

				horEnds[horEndsSz++] = p;
				horEnds[horEndsSz++] = q;
			}
		}

		verEvs = Arrays.copyOf(verEvs, verEvsSz);
		horEvs = Arrays.copyOf(horEvs, horEvsSz);

		Arrays.sort(verEvs, new Comparator<Event>() {

			@Override
			public int compare(Event o1, Event o2) {
				return Integer.compare(o1.seg.p.x, o2.seg.p.x);
			}

		});

		Arrays.sort(horEvs);

		horEnds = Arrays.copyOf(horEnds, horEndsSz);
		Arrays.sort(horEnds, byYThenX);
		verEnds = Arrays.copyOf(verEnds, verEndsSz);
		Arrays.sort(verEnds, byXThenY);

		allX = unique(allX);
		int cntX = allX.length;

		K = (int) Math.sqrt(cntX);

		Segment[] hors = new Segment[n];
		int horsSz = 0;

		TreeSet<Segment> vers = new TreeSet<>();

		Event[] stripEvs = new Event[2 * n];
		int stripEvsSz = 0;

		int ptrFrom = 0;

		for (int i = 0; i < cntX; i += K) {

			// System.err.println(i);

			int left = allX[i];
			int right = allX[Math.min(i + K, cntX - 1)];

			horsSz = 0;
			vers.clear();

			while (ptrFrom < verEvsSz && verEvs[ptrFrom].seg.p.x < left) {
				ptrFrom++;
			}

			int ptrStrip = ptrFrom;
			stripEvsSz = 0;

			while (ptrStrip < verEvsSz && verEvs[ptrStrip].seg.p.x <= right) {
				stripEvs[stripEvsSz++] = verEvs[ptrStrip++];
			}

			Arrays.sort(stripEvs, 0, stripEvsSz);

			int horPtr = 0;
			int verPtr = 0;

			while (horPtr < horEvsSz || verPtr < stripEvsSz) {

				Event curHorEv = horPtr == horEvsSz ? null : horEvs[horPtr];
				Event curVerEv = verPtr == stripEvsSz ? null : stripEvs[verPtr];

				if (curVerEv == null
						|| (curHorEv != null && curHorEv.y < curVerEv.y)) {

					Event ev = curHorEv;

					int xFrom = ev.seg.p.x;
					int xTo = ev.seg.q.x;
					if (xTo < left || xFrom > right) {
						horPtr++;
						continue;
					}

					if (xFrom <= left && xTo >= right) {
						hors[horsSz++] = ev.seg;
					} else {
						flushGrid(hors, horsSz, vers, ev.seg);
						horsSz = 0;
					}

					horPtr++;
				} else {
					Event ev = curVerEv;
					flushGrid(hors, horsSz, vers, null);
					horsSz = 0;

					if (ev.type == 1) {
						vers.add(ev.seg);
					} else {
						vers.remove(ev.seg);
					}
					verPtr++;
				}

			}

			flushGrid(hors, horsSz, vers, null);

		}

		// int fromX = nextInt();
		// int fromY = nextInt();
		// int toX = nextInt();
		// int toY = nextInt();

		// int fromX = a[0].p.x;
		// int fromY = a[0].p.y;
		// int toX = a[1].q.x;
		// int toY = a[1].q.y;

		// int fromX = a[0].p.x;
		// int fromY = a[0].p.y;
		// int toX = -1;
		// int toY = -1;

		Point source = new Point(fromX, fromY);
		Point sink = new Point(toX, toY);

    // System.out.println(source + " --> " + sink);

		lst[lstSz++] = source;
		lst[lstSz++] = sink;

		for (int i = 0; i < n; i++) {
			if (a[i].contains(source) || a[i].contains(sink)) {

				for (int j = 0; j < n; j++) {

					Point tmp = inter(a[i], a[j]);
					if (tmp != null) {
						lst[lstSz++] = tmp;
					}

					tmp = inter(a[j], a[i]);
					if (tmp != null) {
						lst[lstSz++] = tmp;
					}
				}

			}
		}

		// System.err.println("scanline "
		// 		+ (System.currentTimeMillis() - startTime) + " ms");

		buildGraph(sink);

		// System.err.println("graph built " + (System.currentTimeMillis() - startTime)
		// 		+ " ms");
		return shortestPath(source, sink);

		// System.err.println("shortest path found "
		// 		+ (System.currentTimeMillis() - startTime) + " ms");
	}

	static Comparator<Point> byXThenY = new Comparator<Point>() {

		@Override
		public int compare(Point o1, Point o2) {
			if (o1.x != o2.x) {
				return o1.x < o2.x ? -1 : 1;
			}
			return Integer.compare(o1.y, o2.y);
		}
	};

	static Comparator<Point> byYThenX = new Comparator<Point>() {

		@Override
		public int compare(Point o1, Point o2) {
			if (o1.y != o2.y) {
				return o1.y < o2.y ? -1 : 1;
			}
			return Integer.compare(o1.x, o2.x);
		}
	};

	int[] gHead;
	int[] gNext;
	int[] gTo;
	int[] gLen;

	int gSz;

	long[] heur;

	void buildGraph(Point sink) {

		Arrays.sort(lst, 0, lstSz, byXThenY);
		int sz = 1;
		Point last = lst[0];
		for (int i = 1; i < lstSz; i++) {
			Point ith = lst[i];
			if (!ith.sameAs(last)) {
				lst[sz++] = ith;
				last = ith;
			}
		}

		// out.println("unique lst " + (System.currentTimeMillis() - startTime)
		// + " ms");

		lst = Arrays.copyOf(lst, sz);

		heur = new long[sz];

		for (int i = 0; i < sz; i++) {
			lst[i].id = i;
			heur[i] = manhDist(lst[i], sink);
		}

		// System.err.println(Arrays.toString(lst));

		// out.println("size = " + sz);

		// g = new int[sz][8];
		// dblDeg = new int[sz * 8];

		gHead = new int[sz];
		gNext = new int[sz * 4];
		gTo = new int[sz * 4];
		gLen = new int[sz * 4];
		gSz = 0;

		Arrays.fill(gHead, -1);

		// System.err.println(verEnds.length + " - verEnds.length");

		int ptr = 0;
		for (int i = 0; i < sz - 1; i++) {
			while (ptr < verEnds.length
					&& byXThenY.compare(verEnds[ptr], lst[i]) <= 0) {
				ptr += 2;
			}
			if (ptr == 0) {
				continue;
			}

			if (byXThenY.compare(lst[i + 1], verEnds[ptr - 1]) <= 0) {
				connectNodes(lst[i], lst[i + 1]);
			}
		}

		// out.println("vertical segments " + (System.currentTimeMillis() -
		// startTime) + " ms");

		Arrays.sort(lst, byYThenX);
		ptr = 0;
		for (int i = 0; i < sz - 1; i++) {
			while (ptr < horEnds.length
					&& byYThenX.compare(horEnds[ptr], lst[i]) <= 0) {
				ptr += 2;
			}
			if (ptr == 0) {
				continue;
			}

			if (byYThenX.compare(lst[i + 1], horEnds[ptr - 1]) <= 0) {
				connectNodes(lst[i], lst[i + 1]);
			}
		}

		// out.println("horizontal segments " + (System.currentTimeMillis() -
		// startTime) + " ms");
	}

	static class Distance implements Comparable<Distance> {

		long dist;
		int v;

		long key;

		@Override
		public int compareTo(Distance o) {
			return Long.compare(key, o.key);
		}

		public Distance(long dist, int v, long key) {
			this.dist = dist;
			this.v = v;
			this.key = key;
		}
	}

	static int manhDist(Point a, Point b) {
		return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
	}

	long shortestPath(Point source, Point sink) {

		int n = lst.length;
		long[] d = new long[n];

		Arrays.fill(d, INF);

		int s = -1;
		int t = -1;

		for (int i = 0; i < n; i++) {
			if (lst[i].sameAs(source)) {
				s = lst[i].id;
			}

			if (lst[i].sameAs(sink)) {
				t = lst[i].id;
			}
		}

		boolean[] vis = new boolean[n];
		int[] que = new int[n];
		int head = 0, tail = 0;

		boolean canReach = false;
		que[tail++] = s;
		vis[s] = true;
		while (head < tail) {
			int v = que[head++];
			if (v == t) {
				canReach = true;
				break;
			}
			for (int idx = gHead[v]; idx != -1; idx = gNext[idx]) {
				int u = gTo[idx];
				if (!vis[u]) {
					vis[u] = true;
					que[tail++] = u;
				}
			}
		}

		if (!canReach) {
			return -1;
		}

		PriorityQueue<Distance> q = new PriorityQueue<>();
		d[s] = 0;
		q.add(new Distance(0, s, heur[s]));

		while (!q.isEmpty()) {
			Distance tmp = q.poll();
			long dist = tmp.dist;
			int v = tmp.v;

			if (v == t) {
				return dist;
			}

			if (d[v] != dist) {
				continue;
			}

			for (int idx = gHead[v]; idx != -1; idx = gNext[idx]) {

				int u = gTo[idx];
				int len = gLen[idx];

				if (d[u] > dist + len) {
					d[u] = dist + len;
					q.add(new Distance(d[u], u, d[u] + heur[u]));
				}
			}
		}

		throw new AssertionError();

	}

	void connectNodes(Point a, Point b) {
		// System.err.println(a + " " + b);

		int len = Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
		int v = a.id;
		int u = b.id;

		gTo[gSz] = u;
		gLen[gSz] = len;
		gNext[gSz] = gHead[v];
		gHead[v] = gSz++;

		gTo[gSz] = v;
		gLen[gSz] = len;
		gNext[gSz] = gHead[u];
		gHead[u] = gSz++;
	}

	void flushGrid(Segment[] hors, int horsSz, TreeSet<Segment> vers,
			Segment free) {

		// System.err.println(hors);
		// System.err.println(vers);
		// System.err.println(free);
		// System.err.println("----------");

		if (horsSz != 0 && !vers.isEmpty()) {

			Segment low = hors[0];
			Segment high = hors[horsSz - 1];

			Segment left = vers.first();
			Segment right = vers.last();

			// in these loops we don't check if inter returns null
			// because they shouldn't and we'll get an exception
			// while sorting list of points if we'll get null in the list

			for (int i = 0; i < horsSz; i++) {
				Segment seg = hors[i];

				lst[lstSz++] = inter(seg, left);
				if (left != right) {
					lst[lstSz++] = inter(seg, right);
				}
			}

			for (Segment seg : vers) {
				lst[lstSz++] = inter(low, seg);
				if (low != high) {
					lst[lstSz++] = inter(high, seg);
				}

			}
		}

		if (free == null) {
			return;
		}

		// and here it might not intersect
		for (Segment seg : vers) {
			Point tmp = inter(free, seg);
			if (tmp != null) {
				lst[lstSz++] = tmp;
			}
		}

	}

	Point inter(Segment hor, Segment ver) {

		if (hor.p.y != hor.q.y) {
			return null;
		}

		if (ver.p.x != ver.q.x) {
			return null;
		}

		int resX = ver.p.x;
		int resY = hor.p.y;

		if (hor.p.x <= resX && resX <= hor.q.x && ver.p.y <= resY
				&& resY <= ver.q.y) {

			return new Point(resX, resY);
		}

		return null;
	}

	// int K = 200;
	int K;

	int[] unique(int[] a) {
		Arrays.sort(a);
		int sz = 1;
		for (int i = 1; i < a.length; i++) {
			if (a[i] != a[sz - 1]) {
				a[sz++] = a[i];
			}
		}

		return Arrays.copyOf(a, sz);
	}

	walk() {

		// String input = genAlmostGrid(5000);
		// System.err.println(input);

		// br = new BufferedReader(new InputStreamReader(System.in));
		// br = new BufferedReader(new StringReader(input));
		// out = new PrintWriter(System.out);
		// solve();
		// out.close();
	}

	String genAlmostGrid(int n) {
		StringBuilder sb = new StringBuilder();
		sb.append(n * 4);
		sb.append('\n');

		for (int i = 0; i < n; i++) {
			int mid = 1 + rng.nextInt(n - 3);
			sb.append(String.format("%d %d %d %d\n", i, 0, i, mid));
			sb.append(String.format("%d %d %d %d\n", i, mid + 1, i, n - 1));
		}

		for (int i = 0; i < n; i++) {
			int mid = 1 + rng.nextInt(n - 3);
			sb.append(String.format("%d %d %d %d\n", 0, i, mid, i));
			sb.append(String.format("%d %d %d %d\n", mid + 1, i, n - 1, i));
		}
		sb.append(String.format("%d %d %d %d", rng.nextInt(n), rng.nextInt(n),
				rng.nextInt(n), rng.nextInt(n)));
		return sb.toString();
	}

	long startTime = System.currentTimeMillis();

	long min_distance(int[] x, int[] h, int[] orig_l, int[] orig_r, int[] orig_y, int s, int g) {
	  int n = x.length + orig_l.length;
	  int[] x1s = new int[n];
	  int[] y1s = new int[n];
	  int[] x2s = new int[n];
	  int[] y2s = new int[n];
	  int ptr = 0;
	  
	  for (int i = 0; i < x.length; i++) {
	    x1s[ptr] = x[i];
	    y1s[ptr] = 0;
	    x2s[ptr] = x[i];
	    y2s[ptr] = h[i];
	    ptr++;
	  }
	  
	  for (int i = 0; i < orig_l.length; i++) {
	    x1s[ptr] = x[orig_l[i]];
	    y1s[ptr] = orig_y[i];
	    x2s[ptr] = x[orig_r[i]];
	    y2s[ptr] = orig_y[i];
	    ptr++;
	  }
	  
	  int fromX = x[s];
	  int fromY = 0;
	  int toX = x[g];
	  int toY = 0;

    // System.out.println(fromX + " " + fromY + " " + toX + " " + toY);
	  
	  return solve(x1s, y1s, x2s, y2s, fromX, fromY, toX, toY);
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	33544 KB	Output is correct
2	Correct	113 ms	33292 KB	Output is correct
3	Correct	117 ms	33344 KB	Output is correct
4	Correct	117 ms	33348 KB	Output is correct
5	Correct	133 ms	33380 KB	Output is correct
6	Correct	126 ms	33660 KB	Output is correct
7	Correct	135 ms	33772 KB	Output is correct
8	Correct	131 ms	33436 KB	Output is correct
9	Correct	123 ms	33536 KB	Output is correct
10	Correct	127 ms	33912 KB	Output is correct
11	Correct	122 ms	33508 KB	Output is correct
12	Correct	121 ms	33360 KB	Output is correct
13	Correct	120 ms	33476 KB	Output is correct
14	Correct	124 ms	33596 KB	Output is correct
15	Correct	117 ms	33548 KB	Output is correct
16	Correct	120 ms	33416 KB	Output is correct
17	Correct	134 ms	34144 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	115 ms	33308 KB	Output is correct
2	Correct	115 ms	33340 KB	Output is correct
3	Execution timed out	4133 ms	95156 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2326 ms	85552 KB	Output is correct
2	Execution timed out	4051 ms	234640 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2326 ms	85552 KB	Output is correct
2	Execution timed out	4051 ms	234640 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	33544 KB	Output is correct
2	Correct	113 ms	33292 KB	Output is correct
3	Correct	117 ms	33344 KB	Output is correct
4	Correct	117 ms	33348 KB	Output is correct
5	Correct	133 ms	33380 KB	Output is correct
6	Correct	126 ms	33660 KB	Output is correct
7	Correct	135 ms	33772 KB	Output is correct
8	Correct	131 ms	33436 KB	Output is correct
9	Correct	123 ms	33536 KB	Output is correct
10	Correct	127 ms	33912 KB	Output is correct
11	Correct	122 ms	33508 KB	Output is correct
12	Correct	121 ms	33360 KB	Output is correct
13	Correct	120 ms	33476 KB	Output is correct
14	Correct	124 ms	33596 KB	Output is correct
15	Correct	117 ms	33548 KB	Output is correct
16	Correct	120 ms	33416 KB	Output is correct
17	Correct	134 ms	34144 KB	Output is correct
18	Correct	115 ms	33308 KB	Output is correct
19	Correct	115 ms	33340 KB	Output is correct
20	Execution timed out	4133 ms	95156 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-