Submission #921388
Source Code Expand
using System; using System.Linq; using System.Linq.Expressions; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using System.Numerics; using Number = System.Int64; namespace Program { public class Solver { public void Solve() { var n = sc.Integer(); var root = new Trie(); var s = sc.Scan(n); for (int i = 0; i < n; i++) root.Add(s[i]); root.dfs(); var q = sc.Integer(); var ans = new int[q]; var Q = Enumerate(n, x => new List<KeyValuePair<int, string>>()); for (int i = 0; i < q; i++) Q[sc.Integer() - 1].Add(new KeyValuePair<int, string>(i, sc.Scan())); var a = Enumerate(26, x => new int[26]); for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) a[j][k] = 0; var v = root.f(s[i], a); foreach (var kv in Q[i]) { ans[kv.Key] += v + 1; for (int j = 0; j < 26; j++) for (int k = j + 1; k < 26; k++) ans[kv.Key] += a[kv.Value[j] - 'a'][kv.Value[k] - 'a']; } } foreach (var x in ans) IO.Printer.Out.WriteLine(x); } public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput()); static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); } static public void Main() { var solver = new Program.Solver(); solver.Solve(); Program.IO.Printer.Out.Flush(); } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer: StreamWriter { static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; } public static Printer Out { get; set; } public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { } public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { } public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); } public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } public readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) return 0; if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public string ScanLine() { var sb = new StringBuilder(); for (var b = Char(); b != '\n'; b = (char)read()) if (b == 0) break; else if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { if (isEof) return long.MinValue; long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != 0 && b != '-' && (b < '0' || '9' < b)); if (b == 0) return long.MinValue; if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public int Integer() { return (isEof) ? int.MinValue : (int)Long(); } public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; } private T[] enumerate<T>(int n, Func<T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(); return a; } public char[] Char(int n) { return enumerate(n, Char); } public string[] Scan(int n) { return enumerate(n, Scan); } public double[] Double(int n) { return enumerate(n, Double); } public int[] Integer(int n) { return enumerate(n, Integer); } public long[] Long(int n) { return enumerate(n, Long); } } } #endregion #region Trie public class Trie { public bool ok; public int val; public Trie par; public Trie[] next = new Trie[26]; public void Add(string s) { var t = this; for (int i = 0; i < s.Length; i++) { var v = s[i] - 'a'; if (t.next[v] == null) t.next[v] = new Trie() { par = t }; t = t.next[v]; } t.ok = true; t.val++; } public int dfs() { for (int i = 0; i < 26; i++) if (next[i] != null) val += next[i].dfs(); return val; } public int f(string s, int[][] a) { var ret = 0; var t = this; for (int i = 0; i < s.Length; i++) { if (t.ok) ret++; var v = s[i] - 'a'; for (int j = 0; j < 26; j++) { if (v == j) continue; if (t.next[j] == null) continue; a[j][v] += t.next[j].val; } t = t.next[v]; } return ret; } } #endregion
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | camypaper |
Language | C# (Mono 4.6.2.0) |
Score | 1100 |
Code Size | 6735 Byte |
Status | AC |
Exec Time | 742 ms |
Memory | 151648 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1100 / 1100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 697 ms | 58992 KB |
02.txt | AC | 705 ms | 58740 KB |
03.txt | AC | 683 ms | 58740 KB |
04.txt | AC | 685 ms | 58736 KB |
05.txt | AC | 742 ms | 112372 KB |
06.txt | AC | 706 ms | 138632 KB |
07.txt | AC | 696 ms | 139272 KB |
08.txt | AC | 675 ms | 141704 KB |
09.txt | AC | 673 ms | 141720 KB |
10.txt | AC | 673 ms | 143512 KB |
11.txt | AC | 421 ms | 32256 KB |
12.txt | AC | 465 ms | 37400 KB |
13.txt | AC | 520 ms | 43464 KB |
14.txt | AC | 659 ms | 134032 KB |
15.txt | AC | 672 ms | 141456 KB |
16.txt | AC | 672 ms | 143512 KB |
17.txt | AC | 683 ms | 151648 KB |
18.txt | AC | 308 ms | 21144 KB |
19.txt | AC | 309 ms | 21016 KB |
20.txt | AC | 313 ms | 21264 KB |
21.txt | AC | 312 ms | 21272 KB |
22.txt | AC | 314 ms | 21272 KB |
23.txt | AC | 477 ms | 43736 KB |
24.txt | AC | 429 ms | 32392 KB |
25.txt | AC | 467 ms | 37576 KB |
26.txt | AC | 302 ms | 21144 KB |
27.txt | AC | 358 ms | 33772 KB |
28.txt | AC | 384 ms | 39140 KB |
29.txt | AC | 351 ms | 37860 KB |
30.txt | AC | 453 ms | 48620 KB |
31.txt | AC | 418 ms | 58024 KB |
32.txt | AC | 373 ms | 47324 KB |
33.txt | AC | 413 ms | 63664 KB |
34.txt | AC | 403 ms | 59440 KB |
35.txt | AC | 448 ms | 68512 KB |
36.txt | AC | 703 ms | 64296 KB |
37.txt | AC | 482 ms | 85996 KB |
38.txt | AC | 481 ms | 85996 KB |
39.txt | AC | 24 ms | 2904 KB |
40.txt | AC | 24 ms | 2904 KB |
s1.txt | AC | 24 ms | 2904 KB |
s2.txt | AC | 24 ms | 2904 KB |