結果
問題 | No.1091 Range Xor Query |
ユーザー | fairy_lettuce |
提出日時 | 2020-06-24 01:51:27 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 459 ms / 2,000 ms |
コード長 | 3,439 bytes |
コンパイル時間 | 2,340 ms |
コンパイル使用メモリ | 109,700 KB |
実行使用メモリ | 45,800 KB |
最終ジャッジ日時 | 2023-09-16 20:27:23 |
合計ジャッジ時間 | 12,992 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 57 ms
20,752 KB |
testcase_01 | AC | 58 ms
18,712 KB |
testcase_02 | AC | 58 ms
20,708 KB |
testcase_03 | AC | 143 ms
38,740 KB |
testcase_04 | AC | 264 ms
29,096 KB |
testcase_05 | AC | 339 ms
40,724 KB |
testcase_06 | AC | 80 ms
22,328 KB |
testcase_07 | AC | 318 ms
33,224 KB |
testcase_08 | AC | 428 ms
32,888 KB |
testcase_09 | AC | 232 ms
28,008 KB |
testcase_10 | AC | 332 ms
37,820 KB |
testcase_11 | AC | 411 ms
39,372 KB |
testcase_12 | AC | 284 ms
42,648 KB |
testcase_13 | AC | 446 ms
31,968 KB |
testcase_14 | AC | 352 ms
41,800 KB |
testcase_15 | AC | 373 ms
41,924 KB |
testcase_16 | AC | 322 ms
28,148 KB |
testcase_17 | AC | 459 ms
41,168 KB |
testcase_18 | AC | 120 ms
28,324 KB |
testcase_19 | AC | 157 ms
34,060 KB |
testcase_20 | AC | 421 ms
35,464 KB |
testcase_21 | AC | 216 ms
28,308 KB |
testcase_22 | AC | 435 ms
40,152 KB |
testcase_23 | AC | 378 ms
43,680 KB |
testcase_24 | AC | 384 ms
45,800 KB |
testcase_25 | AC | 387 ms
39,740 KB |
testcase_26 | AC | 384 ms
43,812 KB |
testcase_27 | AC | 386 ms
43,748 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; using System.Linq; namespace AtCoder.Contest.D { static class Program { public static void Solve(Scanner cin) { int n = cin.ReadInt(); int q = cin.ReadInt(); var a = cin.ReadIntArray(n); var st = new Segtree<int>(n, (i, j) => i ^ j, 0); for (int i = 0; i < n; i++) { st.update(i, a[i]); } for (int i = 0; i < q; i++) { int l = cin.ReadInt() - 1; int r = cin.ReadInt() - 1; Console.WriteLine(st.run(l, r + 1)); } } public static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); var cin = new Scanner(); Solve(cin); Console.Out.Flush(); } } class Segtree<T> { int n; T[] tree; Func<T, T, T> f; T exnum; public Segtree(int m, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ex; } public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex) { for (int i = 0; i < m; ++i) tree[i + n - 1] = ini; all_update(); } public void assign_without_update(int j, T x) { tree[j + n - 1] = x; } public void update(int j, T x) { int i = j + n - 1; tree[i] = x; while (i > 0) { i = (i - 1) >> 1; tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } } public void all_update() { for (int i = n - 2; i >= 0; i--) tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } public T look(int i) { return tree[i + n - 1]; } // [s, t) public T run(int s, int t) { return query(s, t, 0, 0, n); } T query(int s, int t, int k, int l, int r) { if (r <= s || t <= l) return exnum; if (s <= l && r <= t) return tree[k]; return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r)); } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string Read() => ReadString(); public string ReadString() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); if (s.Length == 0) return ReadString(); i = 0; return s[i++]; } public string[] ReadStringArray(int N) { string[] Array = new string[N]; for (int i = 0; i < N; i++) { Array[i] = ReadString(); } return Array; } public int ReadInt() { return int.Parse(ReadString()); } public int[] ReadIntArray(int N, int add = 0) { int[] Array = new int[N]; for (int i = 0; i < N; i++) { Array[i] = ReadInt() + add; } return Array; } public long ReadLong() { return long.Parse(ReadString()); } public long[] ReadLongArray(int N, long add = 0) { long[] Array = new long[N]; for (int i = 0; i < N; i++) { Array[i] = ReadLong() + add; } return Array; } public double ReadDouble() { return double.Parse(ReadString()); } public double[] ReadDoubleArray(int N, double add = 0) { double[] Array = new double[N]; for (int i = 0; i < N; i++) { Array[i] = ReadDouble() + add; } return Array; } public T1 ReadValue<T1>() => (T1)Convert.ChangeType(ReadString(), typeof(T1)); } }