Submission #27735789

Source Code Expand

(N,M,D),*XV = $<.map{|ln| ln.split.map(&:to_i) }

X,V = XV.sort_by!(&:first).transpose
X<<1.0/0<<-1.0/0

LR = lambda{|v|
	ls,j = [0]*(N+1),-1
	0.upto(N-1){|i|
		ls[i] = if V[i]<v
			then
				ls[i-1]
			else
				x = X[i]-D
				j += 1 until x<X[j]
				[ls[j-1]+1,ls[i-1]].max
			end
	}

	rs,j = [0]*(N+1),N
	(N-1).downto(0){|i|
		rs[i] = if V[i]<v
			then
				rs[i] = rs[i+1]
			else
				x = X[i]+D
				j -= 1 until X[j]<x
				[rs[j+1]+1,rs[i+1]].max
			end
	}

	next ls,rs
}

p V.sort.reverse.bsearch{|v|
	ls,rs = LR[v]
	next N.times.any?{|i|
		v<=V[i] && M<ls[i]+rs[i]
	}
}||-1

Submission Info

Submission Time
Task D - 展覧会 2 (Exhibition 2)
User ds14050
Language Ruby (2.7.1)
Score 100
Code Size 617 Byte
Status AC
Exec Time 792 ms
Memory 50584 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4 Subtask5 Subtask6
Score / Max Score 0 / 0 3 / 3 12 / 12 19 / 19 17 / 17 22 / 22 27 / 27
Status
AC × 5
AC × 8
AC × 10
AC × 17
AC × 8
AC × 36
AC × 67
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Subtask1 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt
Subtask2 sample-02.txt, 01-01.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt
Subtask3 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 02-01.txt, 02-02.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt
Subtask4 sample-04.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt
Subtask5 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 02-01.txt, 02-02.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 05-01.txt, 05-02.txt, 05-03.txt, 05-04.txt, 05-05.txt, 05-06.txt, 05-07.txt, 05-08.txt, 05-09.txt, 05-10.txt, 05-11.txt, 05-12.txt
Subtask6 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 05-01.txt, 05-02.txt, 05-03.txt, 05-04.txt, 05-05.txt, 05-06.txt, 05-07.txt, 05-08.txt, 05-09.txt, 05-10.txt, 05-11.txt, 05-12.txt, 06-01.txt, 06-02.txt, 06-03.txt, 06-04.txt, 06-05.txt, 06-06.txt, 06-07.txt, 06-08.txt, 06-09.txt, 06-10.txt, 06-11.txt, 06-12.txt, 06-13.txt, 06-14.txt, 06-15.txt, 06-16.txt, 06-17.txt, 06-18.txt, 06-19.txt, 06-20.txt, 06-21.txt, 06-22.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01-01.txt AC 59 ms 14228 KiB
01-02.txt AC 59 ms 14196 KiB
01-03.txt AC 60 ms 14260 KiB
01-04.txt AC 61 ms 14304 KiB
01-05.txt AC 480 ms 41404 KiB
01-06.txt AC 529 ms 41448 KiB
01-07.txt AC 694 ms 41368 KiB
02-01.txt AC 56 ms 14216 KiB
02-02.txt AC 59 ms 14168 KiB
02-03.txt AC 783 ms 41560 KiB
02-04.txt AC 760 ms 39916 KiB
02-05.txt AC 757 ms 40024 KiB
02-06.txt AC 766 ms 41564 KiB
02-07.txt AC 642 ms 41520 KiB
02-08.txt AC 732 ms 39936 KiB
03-01.txt AC 57 ms 14112 KiB
03-02.txt AC 61 ms 14268 KiB
03-03.txt AC 60 ms 14240 KiB
03-04.txt AC 57 ms 14196 KiB
03-05.txt AC 60 ms 14144 KiB
03-06.txt AC 57 ms 14212 KiB
04-01.txt AC 64 ms 14564 KiB
04-02.txt AC 63 ms 14380 KiB
04-03.txt AC 62 ms 14468 KiB
04-04.txt AC 63 ms 14296 KiB
04-05.txt AC 63 ms 14500 KiB
04-06.txt AC 65 ms 14472 KiB
04-07.txt AC 64 ms 14432 KiB
05-01.txt AC 61 ms 14224 KiB
05-02.txt AC 58 ms 14292 KiB
05-03.txt AC 63 ms 14340 KiB
05-04.txt AC 63 ms 14380 KiB
05-05.txt AC 62 ms 14212 KiB
05-06.txt AC 61 ms 14496 KiB
05-07.txt AC 63 ms 14416 KiB
05-08.txt AC 62 ms 14356 KiB
05-09.txt AC 65 ms 14396 KiB
05-10.txt AC 64 ms 14380 KiB
05-11.txt AC 64 ms 14384 KiB
05-12.txt AC 65 ms 14548 KiB
06-01.txt AC 567 ms 41420 KiB
06-02.txt AC 576 ms 41484 KiB
06-03.txt AC 560 ms 39864 KiB
06-04.txt AC 589 ms 41232 KiB
06-05.txt AC 600 ms 40108 KiB
06-06.txt AC 638 ms 41524 KiB
06-07.txt AC 600 ms 41396 KiB
06-08.txt AC 689 ms 40052 KiB
06-09.txt AC 744 ms 41284 KiB
06-10.txt AC 722 ms 39836 KiB
06-11.txt AC 712 ms 40120 KiB
06-12.txt AC 749 ms 41372 KiB
06-13.txt AC 561 ms 50584 KiB
06-14.txt AC 529 ms 39824 KiB
06-15.txt AC 672 ms 39940 KiB
06-16.txt AC 709 ms 41420 KiB
06-17.txt AC 651 ms 39732 KiB
06-18.txt AC 668 ms 41392 KiB
06-19.txt AC 792 ms 39652 KiB
06-20.txt AC 636 ms 41572 KiB
06-21.txt AC 552 ms 41436 KiB
06-22.txt AC 784 ms 39872 KiB
sample-01.txt AC 56 ms 14212 KiB
sample-02.txt AC 59 ms 14260 KiB
sample-03.txt AC 59 ms 14032 KiB
sample-04.txt AC 59 ms 14192 KiB
sample-05.txt AC 60 ms 14164 KiB