#557766 (Java21) No.274 The Wall

提出ソース
結果

問題	No.274 The Wall
ユーザー	narushimas
提出日時	2020-09-25 13:13:53
言語	Java21 (openjdk 21)
結果	AC
実行時間	742 ms / 2,000 ms
コード長	13,989 bytes
コンパイル時間	6,876 ms
コンパイル使用メモリ	79,536 KB
実行使用メモリ	317,688 KB
最終ジャッジ日時	2023-09-10 14:30:44
合計ジャッジ時間	12,901 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	44 ms 49,376 KB
testcase_01	AC	46 ms 49,544 KB
testcase_02	AC	45 ms 49,620 KB
testcase_03	AC	412 ms 193,684 KB
testcase_04	AC	45 ms 49,488 KB
testcase_05	AC	45 ms 49,688 KB
testcase_06	AC	45 ms 49,532 KB
testcase_07	AC	44 ms 49,920 KB
testcase_08	AC	45 ms 49,400 KB
testcase_09	AC	45 ms 49,820 KB
testcase_10	AC	44 ms 49,932 KB
testcase_11	AC	742 ms 317,688 KB
testcase_12	AC	203 ms 54,680 KB
testcase_13	AC	60 ms 52,740 KB
testcase_14	AC	119 ms 55,132 KB
testcase_15	AC	148 ms 55,476 KB
testcase_16	AC	462 ms 175,632 KB
testcase_17	AC	439 ms 164,012 KB
testcase_18	AC	483 ms 162,516 KB
testcase_19	AC	183 ms 55,584 KB
testcase_20	AC	198 ms 55,884 KB
testcase_21	AC	202 ms 55,688 KB
testcase_22	AC	204 ms 55,644 KB
testcase_23	AC	205 ms 55,568 KB
testcase_24	AC	205 ms 55,552 KB
testcase_25	AC	208 ms 53,660 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.*;
import java.util.*;

class TwoSAT {
	private final int n;
	private final InternalSCC scc;
	private final boolean[] answer;

	private boolean hasCalledSatisfiable = false;
	private boolean existsAnswer = false;

	public TwoSAT(int n) {
		this.n = n;
		this.scc = new InternalSCC(2 * n);
		this.answer = new boolean[n];
	}

	public void addClause(int x, boolean f, int y, boolean g) {
		rangeCheck(x);
		rangeCheck(y);
		scc.addEdge(x << 1 | (f ? 0 : 1), y << 1 | (g ? 1 : 0));
		scc.addEdge(y << 1 | (g ? 0 : 1), x << 1 | (f ? 1 : 0));
	}

	public void addImplication(int x, boolean f, int y, boolean g) {
		addClause(x, !f, y, g);
	}

	public void addNand(int x, boolean f, int y, boolean g) {
		addClause(x, !f, y, !g);
	}

	public boolean satisfiable() {
		hasCalledSatisfiable = true;
		int[] ids = scc.ids();
		for (int i = 0; i < n; i++) {
			if (ids[i << 1 | 0] == ids[i << 1 | 1])
				return existsAnswer = false;
			answer[i] = ids[i << 1 | 0] < ids[i << 1 | 1];
		}
		return existsAnswer = true;
	}

	public boolean[] answer() {
		if (!hasCalledSatisfiable) {
			throw new UnsupportedOperationException("Call TwoSAT#satisfiable at least once before TwoSAT#answer.");
		}
		if (existsAnswer)
			return answer;
		return null;
	}

	private void rangeCheck(int x) {
		if (x < 0 || x >= n) {
			throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", x, n));
		}
	}

	private static final class EdgeList {
		long[] a;
		int ptr = 0;

		EdgeList(int cap) {
			a = new long[cap];
		}

		void add(int upper, int lower) {
			if (ptr == a.length)
				grow();
			a[ptr++] = (long) upper << 32 | lower;
		}

		void grow() {
			long[] b = new long[a.length << 1];
			System.arraycopy(a, 0, b, 0, a.length);
			a = b;
		}
	}

	private static final class InternalSCC {
		final int n;
		int m;
		final EdgeList unorderedEdges;
		final int[] start;

		InternalSCC(int n) {
			this.n = n;
			this.unorderedEdges = new EdgeList(n);
			this.start = new int[n + 1];
		}

		void addEdge(int from, int to) {
			unorderedEdges.add(from, to);
			start[from + 1]++;
			this.m++;
		}

		static final long mask = 0xffff_ffffl;

		int[] ids() {
			for (int i = 1; i <= n; i++) {
				start[i] += start[i - 1];
			}
			int[] orderedEdges = new int[m];
			int[] count = new int[n + 1];
			System.arraycopy(start, 0, count, 0, n + 1);
			for (int i = 0; i < m; i++) {
				long e = unorderedEdges.a[i];
				orderedEdges[count[(int) (e >>> 32)]++] = (int) (e & mask);
			}
			int nowOrd = 0;
			int groupNum = 0;
			int k = 0;
			int[] par = new int[n];
			int[] vis = new int[n];
			int[] low = new int[n];
			int[] ord = new int[n];
			java.util.Arrays.fill(ord, -1);
			int[] ids = new int[n];
			long[] stack = new long[n];
			int ptr = 0;

			for (int i = 0; i < n; i++) {
				if (ord[i] >= 0)
					continue;
				par[i] = -1;
				stack[ptr++] = i;
				while (ptr > 0) {
					long p = stack[--ptr];
					int u = (int) (p & mask);
					int j = (int) (p >>> 32);
					if (j == 0) {
						low[u] = ord[u] = nowOrd++;
						vis[k++] = u;
					}
					if (start[u] + j < count[u]) {
						int to = orderedEdges[start[u] + j];
						stack[ptr++] += 1l << 32;
						if (ord[to] == -1) {
							stack[ptr++] = to;
							par[to] = u;
						} else {
							low[u] = Math.min(low[u], ord[to]);
						}
					} else {
						while (j-- > 0) {
							int to = orderedEdges[start[u] + j];
							if (par[to] == u)
								low[u] = Math.min(low[u], low[to]);
						}
						if (low[u] == ord[u]) {
							while (true) {
								int v = vis[--k];
								ord[v] = n;
								ids[v] = groupNum;
								if (v == u)
									break;
							}
							groupNum++;
						}
					}
				}
			}
			for (int i = 0; i < n; i++) {
				ids[i] = groupNum - 1 - ids[i];
			}
			return ids;
		}
	}
}

public class Main {
	static int m;
	static void solve() {
		int n = ni();
		m = ni();
		var p = na(n, 2);
		var ts = new TwoSAT(n); //そのまま　true ひっくり返す　false
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				int[] a = p[i], b = p[j];
				if(overlap(a[0], a[1], b[0], b[1])) ts.addClause(i, false, j, false);
				if(overlap(a[0], a[1], rev(b[1]), rev(b[0]))) ts.addClause(i, false, j, true);
				if(overlap(rev(a[1]), rev(a[0]), b[0], b[1])) ts.addClause(i, true, j, false);
				if(overlap(rev(a[1]), rev(a[0]), rev(b[1]), rev(b[0]))) ts.addClause(i, true, j, true);
			}
		}
		if(!ts.satisfiable()) {
			out.println("NO");
			return;
		}
		out.println("YES");
		
	}
	
	static int rev(int x) {
		return m - 1 - x;
	}

	static boolean overlap (int l1, int r1, int l2, int r2) {
		int[] a = {l1, r1}, b = {l2, r2};
		if(l1 > l2) {
			var t = a.clone();
			a = b;
			b = t;
		}
		return a[1] >= b[0];
	}
	
	//constants
	static final int inf = Integer.MAX_VALUE / 2;
	static final long linf = Long.MAX_VALUE / 3;
	static final double dinf = Double.MAX_VALUE / 3;
	static final long mod = (long) 1e9 + 7;
	static final int[] dx = { -1, 0, 1, 0 }, dy = { 0, -1, 0, 1 }, dx8 = { -1, -1, -1, 0, 0, 1, 1, 1 },
			dy8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
	static final double eps = 1e-10;

	//libraries
	static long[] cum(int a[]) {
		long[] cum = new long[a.length + 1];
		for (int i = 0; i < a.length; i++)
			cum[i + 1] = cum[i] + a[i];
		return cum;
	}

	static long[] cum(long a[]) {
		long[] cum = new long[a.length + 1];
		for (int i = 0; i < a.length; i++)
			cum[i + 1] = cum[i] + a[i];
		return cum;
	}

	static void reverse(int ar[]) {
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			int t = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = t;
		}
	}

	static void reverse(long ar[]) {
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			long t = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = t;
		}
	}

	static void reverse(double ar[]) {
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			double t = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = t;
		}
	}

	static void reverse(char ar[]) {
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			char t = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = t;
		}
	}

	static String getReverse(String s) {
		StringBuilder sb = new StringBuilder(s);
		return sb.reverse().toString();
	}

	static <T> void reverse(T[] ar) {
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			T t = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = t;
		}
	}

	static int[] concat(int x, int arr[]) {
		int ret[] = new int[arr.length + 1];
		System.arraycopy(arr, 0, ret, 1, ret.length - 1);
		ret[0] = x;
		return ret;
	}

	static int[] concat(int arr[], int x) {
		int ret[] = new int[arr.length + 1];
		System.arraycopy(arr, 0, ret, 0, ret.length - 1);
		ret[ret.length - 1] = x;
		return ret;
	}

	static long[] concat(long x, long arr[]) {
		long ret[] = new long[arr.length + 1];
		System.arraycopy(arr, 0, ret, 1, ret.length - 1);
		ret[0] = x;
		return ret;
	}

	static long[] concat(long arr[], long x) {
		long ret[] = new long[arr.length + 1];
		System.arraycopy(arr, 0, ret, 0, ret.length - 1);
		ret[ret.length - 1] = x;
		return ret;
	}

	static char[] concat(char x, char arr[]) {
		char ret[] = new char[arr.length + 1];
		System.arraycopy(arr, 0, ret, 0, ret.length - 1);
		ret[ret.length - 1] = x;
		return ret;
	}

	static char[] concat(char arr[], char x) {
		char ret[] = new char[arr.length + 1];
		System.arraycopy(arr, 0, ret, 0, ret.length - 1);
		ret[ret.length - 1] = x;
		return ret;
	}

	static int max(int x, int y) {
		return Math.max(x, y);
	}

	static int min(int x, int y) {
		return Math.min(x, y);
	}

	static int max(int x, int y, int z) {
		x = Math.max(x, y);
		x = Math.max(x, z);
		return x;
	}

	static int min(int x, int y, int z) {
		x = Math.min(x, y);
		x = Math.min(x, z);
		return x;
	}

	static long max(long x, long y) {
		return Math.max(x, y);
	}

	static long min(long x, long y) {
		return Math.min(x, y);
	}

	static long max(long x, long y, long z) {
		x = Math.max(x, y);
		x = Math.max(x, z);
		return x;
	}

	static long min(long x, long y, long z) {
		x = Math.min(x, y);
		x = Math.min(x, z);
		return x;
	}

	static double max(double x, double y) {
		return Math.max(x, y);
	}

	static double min(double x, double y) {
		return Math.min(x, y);
	}

	static double max(double x, double y, double z) {
		x = Math.max(x, y);
		x = Math.max(x, z);
		return x;
	}

	static double min(double x, double y, double z) {
		x = Math.min(x, y);
		x = Math.min(x, z);
		return x;
	}

	static void sort(int[] ar) {
		Arrays.sort(ar);
	}

	static void sort(long[] ar) {
		Arrays.sort(ar);
	}

	static void sort(double[] ar) {
		Arrays.sort(ar);
	}

	static void sort(char[] ar) {
		Arrays.sort(ar);
	}

	static void rsort(int[] ar) {
		Arrays.sort(ar);
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			int tmp = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = tmp;
		}
	}

	static void rsort(long[] ar) {
		Arrays.sort(ar);
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			long tmp = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = tmp;
		}
	}

	static void rsort(double[] ar) {
		Arrays.sort(ar);
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			double tmp = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = tmp;
		}
	}

	static void rsort(char[] ar) {
		Arrays.sort(ar);
		int len = ar.length;
		for (int i = 0; i < len / 2; i++) {
			char tmp = ar[i];
			ar[i] = ar[len - 1 - i];
			ar[len - 1 - i] = tmp;
		}
	}

	static void fill(int arr[], int x) {
		Arrays.fill(arr, x);
	}

	static void fill(long arr[], long x) {
		Arrays.fill(arr, x);
	}

	static void fill(boolean arr[], boolean x) {
		Arrays.fill(arr, x);
	}

	static void fill(double arr[], double x) {
		Arrays.fill(arr, x);
	}

	static void fill(int arr[][], int x) {
		for (int i = 0; i < arr.length; i++)
			Arrays.fill(arr[i], x);
	}

	static void fill(long arr[][], long x) {
		for (int i = 0; i < arr.length; i++)
			Arrays.fill(arr[i], x);
	}

	static void fill(double arr[][], double x) {
		for (int i = 0; i < arr.length; i++)
			Arrays.fill(arr[i], x);
	}

	static void fill(boolean arr[][], boolean x) {
		for (int i = 0; i < arr.length; i++)
			Arrays.fill(arr[i], x);
	}

	//MOD culc
	static long plus(long x, long y) {
		long res = (x + y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long sub(long x, long y) {
		long res = (x - y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long mul(long x, long y) {
		long res = (x * y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long div(long x, long y) {
		long res = x * pow(y, mod - 2) % mod;
		return res < 0 ? res + mod : res;
	}

	static long pow(long x, long y) {
		if (y < 0)
			return 0;
		if (y == 0)
			return 1;
		if (y % 2 == 1)
			return (x * pow(x, y - 1)) % mod;
		long root = pow(x, y / 2);
		return root * root % mod;
	}

	public static void main(String[] args) throws Exception {
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	//input
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;

	private static int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private static boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

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

	@SuppressWarnings("unused")
	private static double nd() {
		return Double.parseDouble(ns());
	}

	@SuppressWarnings("unused")
	private static char nc() {
		return (char) skip();
	}

	private static String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private static char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	@SuppressWarnings("unused")
	private static char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	@SuppressWarnings("unused")
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	@SuppressWarnings("unused")
	private static long[] nla(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}

	@SuppressWarnings("unused")
	private static int[][] na(int n, int m) {
		int[][] res = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				res[i][j] = ni();
			}
		}
		return res;
	}

	@SuppressWarnings("unused")
	private static long[][] nla(int n, int m) {
		long[][] res = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				res[i][j] = nl();
			}
		}
		return res;
	}

	private static int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private static long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
}
yukicoder

結果

テストケース

ソースコード
