Submission #17510686

---

Source Code Expand

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class Main {
	
	static final long INF = Long.MAX_VALUE / 5;
	
	long[] go(int[] as, int[] bs) {
		int n = as.length;
		long[] ret = new long[n + 1];
		HashMap<Integer, Integer> memo = new HashMap<>();
		int[] where = new int[n];
		boolean bad = false;
		for (int i = 0; i < n; i++) {
			if (bad) {
				ret[i + 1] = INF;
				continue;
			}
			Integer idx = memo.get(bs[i] - i);
			if (idx == null) {
				if (bs[i] == i + 1) {
					idx = -1;
				} else {
					bad = true;
					ret[i + 1] = INF;
					continue;
				}
			}
			where[i] = idx;
			memo.put(as[i] - i, i);
			if (i == 0) {
				ret[i + 1] = 1;
			} else {
				if (where[i] == where[i - 1]) {
					ret[i + 1] = ret[i] + 1;
				} else {
					ret[i + 1] = ret[i] + (i - where[i]);
				}
			}
		}
		return ret;
	}
	
	long go(int[] as, int[] bs, int left, int right) {
		int n = as.length;
		int[] asLeft = new int[n];
		int[] bsLeft = new int[n];
		for (int i = 0; i < n; i++) {
			asLeft[i] = as[i] - left;
			bsLeft[i] = bs[i] - left;
		}
		
		int[] asRight = new int[n];
		int[] bsRight = new int[n];
		for (int i = 0; i < n; i++) {
			asRight[i] = right - as[n - 1 - i];
			bsRight[i] = right - bs[n - 1 - i];
		}
		
		long[] ansL = go(asLeft, bsLeft);
		long[] ansR = go(asRight, bsRight);
		
		long ret = INF;
		for (int i = 0; i <= n; i++) {
			ret = Math.min(ret, ansL[i] + ansR[n - i]);
		}
		return ret;
	}

	void submit() {
		int n = nextInt();
		int l = nextInt();
		int[] as = new int[n + 2];
		int[] bs = new int[n + 2];
		as[0] = bs[0] = 0;
		as[n + 1] = bs[n + 1] = l + 1;
		for (int i = 1; i <= n; i++) {
			as[i] = nextInt();
		}
		for (int i = 1; i <= n; i++) {
			bs[i] = nextInt();
		}
		
		int last = 0;
		long outp = 0;
		for (int i = 1; i <= n + 1; i++) {
			if (as[i] == bs[i]) {
				if (i > last + 1) {
					long delta = go(Arrays.copyOfRange(as, last + 1, i), Arrays.copyOfRange(bs, last + 1, i), as[last], as[i]);
					if (delta >= INF) {
						out.println(-1);
						return;
					}
					outp += delta;
				}
				last = i;
			}
		}
		
		out.println(outp);
	}

	void test() {

	}

	void stress() {
		for (int tst = 0;; tst++) {
			if (false) {
				throw new AssertionError();
			}
			System.err.println(tst);
		}
	}

	Main() throws IOException {
		is = System.in;
		out = new PrintWriter(System.out);
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();
	static final int C = 5;

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	private InputStream is;
	PrintWriter out;

	private byte[] buf = new byte[1 << 14];
	private int bufSz = 0, bufPtr = 0;

	private int readByte() {
		if (bufSz == -1)
			throw new RuntimeException("Reading past EOF");
		if (bufPtr >= bufSz) {
			bufPtr = 0;
			try {
				bufSz = is.read(buf);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			if (bufSz <= 0)
				return -1;
		}
		return buf[bufPtr++];
	}

	private boolean isTrash(int c) {
		return c < 33 || c > 126;
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isTrash(b))
			;
		return b;
	}

	String nextToken() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	String nextString() {
		int b = readByte();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b) || b == ' ') {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	char nextChar() {
		return (char) skip();
	}

	int nextInt() {
		int ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}

	long nextLong() {
		long ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}
}

Submission Info

Judge Result