Submission #3412533
Source Code Expand
import static java.util.Arrays.*; import static java.util.stream.Collectors.*; import java.util.*; public class Main { private class Data { int n, p; public Data(int n, int p) { this.n = n; this.p = p; } @Override public String toString() { return n + ":" + p; } } private class Range { int src, dst; public Range(int src, int dst) { this.src = src; this.dst = dst; } public int len() { return dst - src + 1; } public boolean isInc(int tgt) { return src <= tgt && tgt <= dst; } @Override public String toString() { return src + "-" + dst; } } public void main(Scanner sc) { int n = sc.nextInt(); int k = sc.nextInt(); int q = sc.nextInt(); int a[] = new int[n]; Data data[] = new Data[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); data[i] = new Data(a[i], i); } sc.close(); sort(data, (o1, o2) -> o1.n - o2.n); Map<Integer, Range> map = new HashMap<>(); map.put(0, new Range(0, n - 1)); int ans = Integer.MAX_VALUE; for (int i = 0; i < n;) { LinkedList<Integer> tmp = new LinkedList<>(); for (Range r : map.values()) { tmp.addAll(stream(copyOfRange(a, r.src, r.dst + 1)).sorted().limit(r.len() - k + 1) .boxed().collect(toList())); } Collections.sort(tmp); if (tmp.size() < q) { break; } int y = tmp.get(q - 1); int x = data[i].n; ans = Math.min(ans, y - x); splash(map, k, data[i].p); while (i < n && data[i].n == x) { splash(map, k, data[i].p); i++; } } System.out.println(ans); } private void splash(Map<Integer, Range> map, int minSize, int p) { for (Range r : new ArrayList<>(map.values())) { if (r.isInc(p)) { Range newR = new Range(p + 1, r.dst); if (newR.len() >= minSize) { map.put(p + 1, newR); } r.dst = p - 1; if (r.len() < minSize) { map.remove(r.src); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); new Main().main(sc); } }
Submission Info
Submission Time | |
---|---|
Task | E - Range Minimum Queries |
User | minorin |
Language | Java8 (OpenJDK 1.8.0) |
Score | 600 |
Code Size | 2735 Byte |
Status | AC |
Exec Time | 1110 ms |
Memory | 93864 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 235 ms | 26836 KB |
sample_02.txt | AC | 179 ms | 26956 KB |
sample_03.txt | AC | 182 ms | 22996 KB |
subtask_1_01.txt | AC | 180 ms | 24404 KB |
subtask_1_02.txt | AC | 183 ms | 23628 KB |
subtask_1_03.txt | AC | 755 ms | 61516 KB |
subtask_1_04.txt | AC | 267 ms | 29268 KB |
subtask_1_05.txt | AC | 192 ms | 25036 KB |
subtask_1_06.txt | AC | 209 ms | 24660 KB |
subtask_1_07.txt | AC | 608 ms | 46212 KB |
subtask_1_08.txt | AC | 266 ms | 29296 KB |
subtask_1_09.txt | AC | 361 ms | 47948 KB |
subtask_1_10.txt | AC | 252 ms | 26132 KB |
subtask_1_11.txt | AC | 353 ms | 36992 KB |
subtask_1_12.txt | AC | 1110 ms | 93864 KB |
subtask_1_13.txt | AC | 717 ms | 50620 KB |
subtask_1_14.txt | AC | 393 ms | 34836 KB |
subtask_1_15.txt | AC | 518 ms | 44404 KB |
subtask_1_16.txt | AC | 250 ms | 30488 KB |
subtask_1_17.txt | AC | 432 ms | 44056 KB |
subtask_1_18.txt | AC | 626 ms | 64896 KB |
subtask_1_19.txt | AC | 738 ms | 63596 KB |
subtask_1_20.txt | AC | 648 ms | 65044 KB |
subtask_1_21.txt | AC | 631 ms | 65372 KB |
subtask_1_22.txt | AC | 270 ms | 26208 KB |
subtask_1_23.txt | AC | 545 ms | 46008 KB |
subtask_1_24.txt | AC | 827 ms | 62816 KB |
subtask_1_25.txt | AC | 380 ms | 41580 KB |
subtask_1_26.txt | AC | 397 ms | 40308 KB |
subtask_1_27.txt | AC | 291 ms | 30924 KB |
subtask_1_28.txt | AC | 272 ms | 29312 KB |
subtask_1_29.txt | AC | 499 ms | 51128 KB |
subtask_1_30.txt | AC | 269 ms | 27336 KB |
subtask_1_31.txt | AC | 403 ms | 36312 KB |
subtask_1_32.txt | AC | 482 ms | 40476 KB |
subtask_1_33.txt | AC | 260 ms | 29252 KB |
subtask_1_34.txt | AC | 265 ms | 27740 KB |
subtask_1_35.txt | AC | 291 ms | 29228 KB |
subtask_1_36.txt | AC | 260 ms | 29384 KB |
subtask_1_37.txt | AC | 391 ms | 40276 KB |
subtask_1_38.txt | AC | 253 ms | 29128 KB |
subtask_1_39.txt | AC | 361 ms | 39768 KB |
subtask_1_40.txt | AC | 244 ms | 29068 KB |
subtask_1_41.txt | AC | 254 ms | 27116 KB |
subtask_1_42.txt | AC | 252 ms | 27368 KB |
subtask_1_43.txt | AC | 255 ms | 29980 KB |
subtask_1_44.txt | AC | 273 ms | 27216 KB |
subtask_1_45.txt | AC | 315 ms | 37204 KB |
subtask_1_46.txt | AC | 261 ms | 27708 KB |
subtask_1_47.txt | AC | 239 ms | 27312 KB |
subtask_1_48.txt | AC | 257 ms | 28764 KB |