結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | 👑 kakel-san |
提出日時 | 2023-10-02 21:03:07 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 3,000 ms |
コード長 | 2,961 bytes |
コンパイル時間 | 3,327 ms |
コンパイル使用メモリ | 69,908 KB |
実行使用メモリ | 118,024 KB |
最終ジャッジ日時 | 2023-10-02 21:03:41 |
合計ジャッジ時間 | 33,429 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
21,856 KB |
testcase_01 | AC | 66 ms
21,972 KB |
testcase_02 | AC | 119 ms
44,160 KB |
testcase_03 | AC | 523 ms
67,188 KB |
testcase_04 | AC | 546 ms
62,032 KB |
testcase_05 | AC | 428 ms
54,500 KB |
testcase_06 | AC | 696 ms
75,084 KB |
testcase_07 | AC | 755 ms
80,320 KB |
testcase_08 | AC | 567 ms
66,648 KB |
testcase_09 | AC | 704 ms
81,108 KB |
testcase_10 | AC | 613 ms
66,276 KB |
testcase_11 | AC | 395 ms
50,240 KB |
testcase_12 | AC | 633 ms
70,572 KB |
testcase_13 | AC | 419 ms
53,236 KB |
testcase_14 | AC | 455 ms
57,992 KB |
testcase_15 | AC | 409 ms
50,380 KB |
testcase_16 | AC | 575 ms
66,596 KB |
testcase_17 | AC | 1,000 ms
93,148 KB |
testcase_18 | AC | 859 ms
90,128 KB |
testcase_19 | AC | 973 ms
95,876 KB |
testcase_20 | AC | 280 ms
53,904 KB |
testcase_21 | AC | 373 ms
62,472 KB |
testcase_22 | AC | 474 ms
55,592 KB |
testcase_23 | AC | 318 ms
54,468 KB |
testcase_24 | AC | 377 ms
50,780 KB |
testcase_25 | AC | 859 ms
77,628 KB |
testcase_26 | AC | 893 ms
87,440 KB |
testcase_27 | AC | 210 ms
35,028 KB |
testcase_28 | AC | 532 ms
74,976 KB |
testcase_29 | AC | 1,012 ms
97,464 KB |
testcase_30 | AC | 856 ms
91,132 KB |
testcase_31 | AC | 523 ms
72,684 KB |
testcase_32 | AC | 1,155 ms
104,724 KB |
testcase_33 | AC | 1,133 ms
118,024 KB |
testcase_34 | AC | 1,114 ms
115,848 KB |
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static long NN => long.Parse(ReadLine()); static long[] NList => ReadLine().Split().Select(long.Parse).ToArray(); static long[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, k, q) = (c[0], (int)c[1], c[2]); var walls = NArr(k); var query = NArr(q); var wlist = new List<(int id, long height)>[n]; var qlist = new List<(int id, long height)>[n]; for (var i = 0; i < n; ++i) { wlist[i] = new List<(int id, long height)>(); qlist[i] = new List<(int id, long height)>(); } for (var i = 0; i < k; ++i) { wlist[walls[i][0] - 1].Add((i, walls[i][3])); if (walls[i][1] < n) wlist[walls[i][1]].Add((i, -walls[i][3])); } for (var i = 0; i < q; ++i) { qlist[query[i][0] - 1].Add((i, query[i][1])); } var ft = new FenwickTree(k + 1); var ans = new long[q]; for (var i = 0; i < n; ++i) { foreach (var w in wlist[i]) { ft.Add(w.id, w.height); } foreach (var qi in qlist[i]) { if (ft.Sum(k) < qi.height) ans[qi.id] = -1; else ans[qi.id] = walls[ft.LowerBound(qi.height)][2]; } } WriteLine(string.Join("\n", ans)); } class FenwickTree { int size; long[] tree; public FenwickTree(int size) { this.size = size; tree = new long[size + 2]; } public void Add(int index, long value) { ++index; for (var x = index; x <= size; x += (x & -x)) tree[x] += value; } /// <summary>先頭からindexまでの和(include index)</summary> public long Sum(int index) { if (index < 0) return 0; ++index; var sum = 0L; for (var x = index; x > 0; x -= (x & -x)) sum += tree[x]; return sum; } /// <summary>Sum(x) >= value となる最小のxを求める</summary> // 各要素は非負であること public int LowerBound(long value) { if (value < 0) return -1; var x = 0; var b = 1; while (b * 2 <= size) b <<= 1; for (var k = b; k > 0; k >>= 1) { if (x + k <= size && tree[x + k] < value) { value -= tree[x + k]; x += k; } } return x; } } }