結果
問題 | No.1997 X Lighting |
ユーザー | 👑 kakel-san |
提出日時 | 2023-10-01 22:07:47 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 542 ms / 2,000 ms |
コード長 | 4,499 bytes |
コンパイル時間 | 2,819 ms |
コンパイル使用メモリ | 68,488 KB |
実行使用メモリ | 65,580 KB |
最終ジャッジ日時 | 2023-10-01 22:08:01 |
合計ジャッジ時間 | 14,228 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
22,916 KB |
testcase_01 | AC | 76 ms
22,772 KB |
testcase_02 | AC | 75 ms
22,844 KB |
testcase_03 | AC | 74 ms
22,864 KB |
testcase_04 | AC | 72 ms
24,888 KB |
testcase_05 | AC | 83 ms
24,916 KB |
testcase_06 | AC | 138 ms
27,456 KB |
testcase_07 | AC | 77 ms
24,916 KB |
testcase_08 | AC | 83 ms
22,880 KB |
testcase_09 | AC | 78 ms
23,024 KB |
testcase_10 | AC | 90 ms
24,932 KB |
testcase_11 | AC | 77 ms
24,908 KB |
testcase_12 | AC | 76 ms
25,016 KB |
testcase_13 | AC | 185 ms
31,340 KB |
testcase_14 | AC | 326 ms
61,468 KB |
testcase_15 | AC | 175 ms
44,408 KB |
testcase_16 | AC | 209 ms
42,800 KB |
testcase_17 | AC | 415 ms
61,720 KB |
testcase_18 | AC | 247 ms
44,220 KB |
testcase_19 | AC | 460 ms
63,864 KB |
testcase_20 | AC | 542 ms
64,936 KB |
testcase_21 | AC | 512 ms
65,580 KB |
testcase_22 | AC | 500 ms
64,032 KB |
testcase_23 | AC | 289 ms
55,408 KB |
testcase_24 | AC | 83 ms
25,660 KB |
testcase_25 | AC | 522 ms
63,200 KB |
testcase_26 | AC | 420 ms
60,252 KB |
testcase_27 | AC | 435 ms
61,732 KB |
testcase_28 | AC | 184 ms
41,856 KB |
testcase_29 | AC | 178 ms
43,580 KB |
testcase_30 | AC | 481 ms
63,440 KB |
testcase_31 | AC | 338 ms
51,036 KB |
testcase_32 | AC | 151 ms
39,548 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[] NMi => ReadLine().Split().Select(c => long.Parse(c) - 1).ToArray(); static long[][] NMap(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = (c[0], c[1]); var map = NMap(m); var pset = new HashSet<long>(); var mset = new HashSet<long>(); var opset = new HashSet<long>(); var omset = new HashSet<long>(); var ecset = new HashSet<long>(); var ocset = new HashSet<long>(); ecset.Add(0); ocset.Add(0); foreach (var mi in map) { pset.Add(mi[0] + mi[1]); mset.Add(mi[0] - mi[1]); if ((mi[0] + mi[1]) % 2 == 0) { ecset.Add(mi[0] + mi[1]); ecset.Add(Math.Abs(mi[0] - mi[1])); ecset.Add(2 * n - 2 - Math.Abs(mi[0] - mi[1])); } else { ocset.Add(mi[0] + mi[1]); ocset.Add(Math.Abs(mi[0] - mi[1])); ocset.Add(2 * n - 2 - Math.Abs(mi[0] - mi[1])); } } var eclist = new List<long>(ecset); eclist.Sort(); var edic = new Dictionary<long, int>(); for (var i = 0; i < eclist.Count; ++i) edic[eclist[i]] = i; var oclist = new List<long>(ocset); oclist.Sort(); var odic = new Dictionary<long, int>(); for (var i = 0; i < oclist.Count; ++i) odic[oclist[i]] = i; var eft = new FenwickTree(eclist.Count); var oft = new FenwickTree(oclist.Count); var ans = 0L; foreach (var plus in pset) { if (plus % 2 == 0) { ans += Math.Min(plus + 1, 2 * n - 1 - plus); // WriteLine($"/: {Math.Min(plus + 1, 2 * n - 1 - plus)}"); eft.Add(edic[plus], 1); } else { ans += Math.Min(plus + 1, 2 * n - 1 - plus); // WriteLine($"/: {Math.Min(plus + 1, 2 * n - 1 - plus)}"); oft.Add(odic[plus], 1); } } foreach (var mi in mset) { var left = Math.Abs(mi); var right = 2 * n - 2 - Math.Abs(mi); if (mi % 2 == 0) { ans += (right - left) / 2 + 1 - eft.Sum(edic[right]) + eft.Sum(edic[left] - 1); // WriteLine($"({right} - {left}) / 2 + 1 - {eft.Sum(edic[right])} + {eft.Sum(edic[left] - 1)}"); } else { ans += (right - left) / 2 + 1 - oft.Sum(odic[right]) + oft.Sum(odic[left] - 1); // WriteLine($"({right} - {left}) / 2 + 1 - {oft.Sum(odic[right])} + {oft.Sum(odic[left] - 1)}"); } } WriteLine(ans); } class FenwickTree { int size; long[] tree; public FenwickTree(int size) { this.size = size; tree = new long[size + 2]; } public void Add(int index, int 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; } } }