結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー | eitaho |
提出日時 | 2016-12-19 22:20:55 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 843 ms / 5,000 ms |
コード長 | 4,940 bytes |
コンパイル時間 | 1,209 ms |
コンパイル使用メモリ | 110,720 KB |
実行使用メモリ | 116,072 KB |
最終ジャッジ日時 | 2024-12-21 16:52:04 |
合計ジャッジ時間 | 18,648 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
18,944 KB |
testcase_01 | AC | 27 ms
19,072 KB |
testcase_02 | AC | 37 ms
20,352 KB |
testcase_03 | AC | 37 ms
20,024 KB |
testcase_04 | AC | 38 ms
20,112 KB |
testcase_05 | AC | 39 ms
20,308 KB |
testcase_06 | AC | 42 ms
20,420 KB |
testcase_07 | AC | 43 ms
20,388 KB |
testcase_08 | AC | 43 ms
20,716 KB |
testcase_09 | AC | 34 ms
19,804 KB |
testcase_10 | AC | 43 ms
20,856 KB |
testcase_11 | AC | 31 ms
19,548 KB |
testcase_12 | AC | 43 ms
21,120 KB |
testcase_13 | AC | 38 ms
20,240 KB |
testcase_14 | AC | 31 ms
19,448 KB |
testcase_15 | AC | 31 ms
19,548 KB |
testcase_16 | AC | 43 ms
20,576 KB |
testcase_17 | AC | 44 ms
20,612 KB |
testcase_18 | AC | 46 ms
20,728 KB |
testcase_19 | AC | 35 ms
19,072 KB |
testcase_20 | AC | 43 ms
21,016 KB |
testcase_21 | AC | 32 ms
19,328 KB |
testcase_22 | AC | 31 ms
18,944 KB |
testcase_23 | AC | 171 ms
33,792 KB |
testcase_24 | AC | 174 ms
34,176 KB |
testcase_25 | AC | 170 ms
34,304 KB |
testcase_26 | AC | 175 ms
33,792 KB |
testcase_27 | AC | 173 ms
34,176 KB |
testcase_28 | AC | 172 ms
33,920 KB |
testcase_29 | AC | 179 ms
33,920 KB |
testcase_30 | AC | 176 ms
34,176 KB |
testcase_31 | AC | 171 ms
34,048 KB |
testcase_32 | AC | 172 ms
33,920 KB |
testcase_33 | AC | 771 ms
116,060 KB |
testcase_34 | AC | 789 ms
116,068 KB |
testcase_35 | AC | 790 ms
116,072 KB |
testcase_36 | AC | 776 ms
115,824 KB |
testcase_37 | AC | 781 ms
116,064 KB |
testcase_38 | AC | 772 ms
112,992 KB |
testcase_39 | AC | 791 ms
112,992 KB |
testcase_40 | AC | 757 ms
113,128 KB |
testcase_41 | AC | 764 ms
113,128 KB |
testcase_42 | AC | 770 ms
112,880 KB |
testcase_43 | AC | 770 ms
113,136 KB |
testcase_44 | AC | 762 ms
113,132 KB |
testcase_45 | AC | 773 ms
112,868 KB |
testcase_46 | AC | 775 ms
112,988 KB |
testcase_47 | AC | 843 ms
112,988 KB |
testcase_48 | AC | 32 ms
18,816 KB |
testcase_49 | AC | 29 ms
19,072 KB |
testcase_50 | AC | 762 ms
112,880 KB |
testcase_51 | AC | 783 ms
113,256 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.Linq;using System.Text;using System.Text.RegularExpressions;using System.Collections.Generic;using System.Diagnostics;using System.Numerics;using Enu = System.Linq.Enumerable;public class Program{Dictionary<long, int> dic = new Dictionary<long, int>();static readonly long Mod0 = (long)1e9 + 7, Mod1 = (long)1e9 + 9;int N;RangeCoefAddSumSegTree seg1, seg2;public void Solve(){N = Reader.Int();int NQ = Reader.Int();var Q = Reader.StringTable(NQ);Init();dic[0] = 0;var ans = new List<int>();for (int qi = 0; qi < NQ; qi++)if (Q[qi][0] == "!") Add(int.Parse(Q[qi][1]), int.Parse(Q[qi][2]), int.Parse(Q[qi][3]), qi + 1);else ans.Add(dic[Key()]);Console.WriteLine(string.Join("\n", ans));}void Init(){var random = new Random();var C = new int[N];long mult = random.Next((int)1e7 + 1, (int)Mod0);for (long i = 0, m = 1; i < N; i++, m = m * mult % Mod0) C[i] = (int)m;seg1 = new RangeCoefAddSumSegTree(N, C, (int)Mod0);mult = random.Next((int)1e7 + 1, (int)Mod1);for (long i = 0, m = 1; i < N; i++, m = m * mult % Mod1) C[i] = (int)m;seg2 = new RangeCoefAddSumSegTree(N, C, (int)Mod1);}long Key() { return seg1.Sum() << 32 | seg2.Sum(); }void Add(int L, int R, int val, int time){seg1.Add(L, R, val);seg2.Add(L, R, val);long key = Key();if (!dic.ContainsKey(key)) dic[key] = time;}}class RangeCoefAddSumSegTree{public readonly int N, Mod;private readonly long[] V, S, Mult;public RangeCoefAddSumSegTree(int n, int[] mult, int mod){for (N = 2; N < n; ) N *= 2;Mod = mod;V = new long[N * 2];S = new long[N * 2];Mult = new long[N + 1];for (int i = 0; i < mult.Length; i++)Mult[i + 1] = (Mult[i] + mult[i]) % Mod;}public long Sum(int L = 0, int R = int.MaxValue) { return Sum(0, 0, N, L, R); }private long Sum(int i, int currL, int currR, int L, int R){if (currL >= R || currR <= L) return 0;if (currL >= L && currR <= R)return ((S[i] + V[i] * (Mod + Mult[currR] - Mult[currL])) % Mod + Mod) % Mod;long res = V[i] * (Mod + Mult[Math.Min(currR, R)] - Mult[Math.Max(currL, L)]) % Mod;int mid = (currL + currR) >> 1;res = (res + Sum(i * 2 + 1, currL, mid, L, R)) % Mod;res = (res + Sum(i * 2 + 2, mid, currR, L, R)) % Mod;return res;}public void Add(int L, int R, long val) { Add(0, val, 0, N, L, R); }private void Add(int i, long val, int currL, int currR, int L, int R){if (currL >= R || currR <= L) return;if (currL >= L && currR <= R) { V[i] = (V[i] + val) % Mod; return; }S[i] = (S[i] + val * (Mod + Mult[Math.Min(currR, R)] - Mult[Math.Max(currL, L)])) % Mod;int mid = currL + currR >> 1;Add(i * 2 + 1, val, currL, mid, L, R);Add(i * 2 + 2, val, mid, currR, L, R);}}class Entry { static void Main() { new Program().Solve(); } }class Reader{static TextReader reader = Console.In;static readonly char[] separator = { ' ' };static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;static string[] A = new string[0];static int i;static void Init() { A = new string[0]; }public static void Set(TextReader r) { reader = r; Init(); }public static void Set(string file) { reader = new StreamReader(file); Init(); }public static bool HasNext() { return CheckNext(); }public static string String() { return Next(); }public static int Int() { return int.Parse(Next()); }public static long Long() { return long.Parse(Next()); }public static double Double() { return double.Parse(Next()); }public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }public static int[] IntArray(int N) { return Range(N, Int); }public static int[][] IntTable(int H) { return Range(H, IntLine); }public static string[] StringArray(int N) { return Range(N, Next); }public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }public static string Line() { return reader.ReadLine().Trim(); }public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }static string[] Split(string s) { return s.Split(separator, op); }static string Next() { CheckNext(); return A[i++]; }static bool CheckNext(){if (i < A.Length) return true;string line = reader.ReadLine();if (line == null) return false;if (line == "") return CheckNext();A = Split(line);i = 0;return true;}}