import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.Scanner; /* * ブロック情報を読み込んだ際に、1.色つきブロック数の多い順にソート 2.ブロックの順方向と逆方向、より色つきブロックの開始が左に来る方向にしたうえで、その位置が左よりのもの順にソート * 1本目はブロック数が最大のものを無条件に選ぶ。 * 2本目以降は向きが固定されるものを優先的に選ぶ。 * 向きが固定されるものを全て選択し終えてもまだブロックが置ける場合、総当たり? * () */ public class Main { private static final String YES = "YES"; private static final String NO = "NO"; private static int n; private static int m; private static boolean[] walledBlocks; private static List blocks; public static void main(String[] args) { Scanner cin = new Scanner(System.in); n = Integer.parseInt(cin.next()); m = Integer.parseInt(cin.next()); walledBlocks = new boolean[m]; blocks = new ArrayList(n); for (int i = 0; i < n; i++) { int[] block = new int[2]; int begin = Integer.parseInt(cin.next()); int end = Integer.parseInt(cin.next()); block[0] = end - begin + 1; /* 180度回転したほうが開始位置が左にくるようであればその向きにしてからリストに詰める */ block[1] = Math.min(begin, m - end - 1); blocks.add(block); } cin.close(); /* リストをソートする。1.ブロック数の多いもの 2. */ Collections.sort(blocks, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o2[0] == o1[0] ? o1[1] - o2[1] : o2[0] - o1[0]; } }); execute(); } private static void execute() { /* まずブロックの1つ目を取ってきて、そのブロックの位置をtrueに更新。処理を終えたらそのブロックを消す */ int[] firstBlock = blocks.get(0); updateWalledBlocks(firstBlock[0], firstBlock[1], walledBlocks); blocks.remove(0); if (!pileUpSingleSideBlocks() || !pileUpDuplicateBlocks() || !pileUpDoubleSideBlocks(blocks, 0, walledBlocks)) { System.out.println(NO); } else { System.out.println(YES); } } private static boolean pileUpSingleSideBlocks() { outer: while (true) { Iterator iterator = blocks.iterator(); while (iterator.hasNext()) { int[] block = iterator.next(); boolean[] canPileUp = canPileUp(block); if (!canPileUp[0] && !canPileUp[1]) { return false; } if (canPileUp[0] && canPileUp[1]) { continue; } if (canPileUp[0]) { updateWalledBlocks(block[0], block[1], walledBlocks); } else { updateWalledBlocks(block[0], m - block[0] - block[1], walledBlocks); } iterator.remove(); continue outer; } return true; } } private static boolean pileUpDuplicateBlocks() { int[] previousBlock = {-1, -1}; List removeIndexes = new ArrayList(); for (int i = 0; i < blocks.size(); i++) { int[] block = blocks.get(i); if (block[0] == previousBlock[0] && block[1] == previousBlock[1]) { boolean[] canPileUp = canPileUp(block); if (!canPileUp[0] || !canPileUp[1]) { return false; } updateWalledBlocks(block[0], block[1], walledBlocks); updateWalledBlocks(block[0], m - block[0] - block[1], walledBlocks); removeIndexes.add(i - 1); removeIndexes.add(i); continue; } previousBlock = block; } for (int i = removeIndexes.size() - 1; i >= 0; i--) { blocks.remove((int) removeIndexes.get(i)); } return true; } private static boolean pileUpDoubleSideBlocks(List restBlocks, int index, boolean[] walledBlocksTemp) { if (index >= restBlocks.size()) { return true; } int[] block = restBlocks.get(index); boolean[] canPileUp = canPileUp(block); if (!canPileUp[0] && !canPileUp[1]) { return false; } if (canPileUp[0]) { boolean[] copyWalled = Arrays.copyOf(walledBlocksTemp, walledBlocksTemp.length); updateWalledBlocks(block[0], block[1], copyWalled); if (pileUpDoubleSideBlocks(restBlocks, index + 1, copyWalled)) { return true; } } if (canPileUp[1]) { boolean[] copyWalled = Arrays.copyOf(walledBlocksTemp, walledBlocksTemp.length); updateWalledBlocks(block[0], m - block[0] - block[1], copyWalled); if (pileUpDoubleSideBlocks(restBlocks, index + 1, copyWalled)) { return true; } } return false; } private static boolean[] canPileUp(int[] block) { boolean[] canPileUp = new boolean[2]; canPileUp[0] = true; canPileUp[1] = true; /* 180度回転しても同じ配置になるブロックだったら、あらかじめcanPileUp[1]をfalseとして片側のみOKにする */ if (block[1] == m - block[0] - block[1]) { canPileUp[1] = false; } for (int i = 0; i < block[0]; i++) { if (walledBlocks[block[1] + i]) { canPileUp[0] = false; } if (walledBlocks[m - block[0] - block[1] + i]) { canPileUp[1] = false; } } return canPileUp; } private static void updateWalledBlocks(int length, int begin, boolean[] targetBlocks) { for (int i = 0; i < length; i++) { targetBlocks[begin + i] = true; } } }