結果

問題 No.580 旅館の予約計画
ユーザー uwi
提出日時 2017-10-22 23:52:08
言語 Java11
(openjdk 11.0.5)
結果
AC  
実行時間 84 ms
コード長 5,765 Byte
コンパイル時間 4,252 ms
使用メモリ 31,360 KB
最終ジャッジ日時 2020-01-01 08:04:00

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
input00.txt AC 76 ms
31,060 KB
input01.txt AC 72 ms
30,912 KB
input02.txt AC 72 ms
31,112 KB
input03.txt AC 72 ms
30,928 KB
input04.txt AC 72 ms
31,148 KB
input05.txt AC 72 ms
30,948 KB
input06.txt AC 72 ms
31,128 KB
input07.txt AC 72 ms
31,096 KB
input08.txt AC 72 ms
30,872 KB
input09.txt AC 76 ms
31,048 KB
input10.txt AC 72 ms
31,112 KB
input11.txt AC 72 ms
30,872 KB
input12.txt AC 72 ms
31,292 KB
input13.txt AC 72 ms
30,880 KB
input14.txt AC 76 ms
31,136 KB
input15.txt AC 84 ms
30,900 KB
input16.txt AC 80 ms
31,192 KB
input17.txt AC 84 ms
31,180 KB
input18.txt AC 80 ms
31,032 KB
input19.txt AC 76 ms
30,920 KB
input20.txt AC 80 ms
30,948 KB
input21.txt AC 80 ms
31,168 KB
input22.txt AC 80 ms
30,896 KB
input23.txt AC 80 ms
31,020 KB
input24.txt AC 80 ms
31,332 KB
input25.txt AC 80 ms
30,932 KB
input26.txt AC 72 ms
30,860 KB
input27.txt AC 72 ms
30,788 KB
input28.txt AC 72 ms
30,996 KB
input29.txt AC 68 ms
30,972 KB
input30.txt AC 76 ms
31,104 KB
input31.txt AC 80 ms
30,920 KB
input32.txt AC 80 ms
30,928 KB
input33.txt AC 80 ms
31,360 KB
input34.txt AC 80 ms
30,968 KB
input35.txt AC 72 ms
31,128 KB
テストケース一括ダウンロード

ソースコード

diff #
package contest171022;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class A {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), m = ni();
		int[][] rs = new int[m][];
		for(int i = 0;i < m;i++){
			rs[i] = new int[]{
					ni()*1440+ni()*60+ni(),
					ni()*1440+ni()*60+ni()+1
			};
		}
		Arrays.sort(rs, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		
		int ans = m;
		MinMaxHeap h = new MinMaxHeap(n+1);
		for(int[] r : rs){
			while(h.pos != 1 && h.min() <= r[0]){
				h.pollMin();
			}
			h.add(r[1]);
			if(h.pos > n+1){
				h.pollMax();
				ans--;
			}
		}
		out.println(ans);
	}
	
	public static class MinMaxHeap {
		public int[] a;
		public int n;
		public int pos;
		public static final int INF = Integer.MAX_VALUE;
		
		public MinMaxHeap(int n)
		{
			this.n = n;
			a = new int[n+1];
			this.pos = 1;
		}
		
		public void add(int x)
		{
			a[pos++] = x;
			int cur = pos-1;
			if(cur == 1)return;
			int par = cur>>>1;
			boolean ofmax = (31-Integer.numberOfLeadingZeros(cur)&1) == 1;
			if(a[cur] < a[par] ^ !ofmax){
				{int d = a[par]; a[par] = a[cur]; a[cur] = d;}
				cur = par;
				for(par = cur>>>2; par >= 1 && a[cur] < a[par] ^ !ofmax;cur>>>=2, par>>>=2){
					int d = a[par]; a[par] = a[cur]; a[cur] = d;
				}
			}else{
				// heapup in minlevel
				for(par = cur>>>2; par >= 1 && a[cur] < a[par] ^ ofmax;cur>>>=2, par>>>=2){
					int d = a[par]; a[par] = a[cur]; a[cur] = d;
				}
			}
		}
		
		public int pollMin()
		{
			int ret = min();
			if(pos >= 2){
				a[1] = a[--pos];
				down(1, false);
			}
			return ret;
		}
		
		private void down(int cur, boolean ofmax)
		{
			while(true){
				int minind = cur;
				if(2*cur < pos && a[2*cur] < a[minind] ^ ofmax)minind = 2*cur;
				if(2*cur+1 < pos && a[2*cur+1] < a[minind] ^ ofmax)minind = 2*cur+1;
				if(4*cur < pos && a[4*cur] < a[minind] ^ ofmax)minind = 4*cur;
				if(4*cur+1 < pos && a[4*cur+1] < a[minind] ^ ofmax)minind = 4*cur+1;
				if(4*cur+2 < pos && a[4*cur+2] < a[minind] ^ ofmax)minind = 4*cur+2;
				if(4*cur+3 < pos && a[4*cur+3] < a[minind] ^ ofmax)minind = 4*cur+3;
				if(minind == cur)break;
				
				{int d = a[cur]; a[cur] = a[minind]; a[minind] = d;}
				
				if(minind >= cur*4 && a[minind>>>1] < a[minind] ^ ofmax){
					int d = a[minind]; a[minind] = a[minind>>>1]; a[minind>>>1] = d;
				}
				cur = minind;
			}
		}
		
		public int min()
		{
			return pos < 2 ? INF : a[1];
		}
		
		public int max()
		{
			return pos < 2 ? INF : pos < 3 ? a[1] : pos < 4 ? a[2] : Math.max(a[2], a[3]);
		}
		
		public int pollMax()
		{
			if(pos < 2)return INF;
			if(pos < 3){
				pos--;
				return a[1];
			}
			if(pos < 4){
				pos--;
				return a[2];
			}
			int maxind = a[3] < a[2] ? 2 : 3;
			int ret = a[maxind];
			a[maxind] = a[--pos];
			down(maxind, true);
			return ret;
		}
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new A().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private 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 boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private 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);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private 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();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0