Submission #921637
Source Code Expand
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <climits> #include <iostream> #include <algorithm> #include <set> #include <map> #include <queue> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> #define DIV 1000000007 using namespace std; long long N; string S[100005]; int k[100005]; string rules[100005]; // ch1 < ch2 なら 小さくなる int memo[100005][26][26]; struct node { node *next[26] = {}; int num[26]; int fin; }; node *root = new node(); void add(string s) { node *curr = root; for (char c : s) { if (curr->next[c - 'a'] == NULL) { curr->next[c - 'a'] = new node(); for(int i = 0; i < 26; i++){ curr->next[c-'a']->num[i] = 0; } curr->next[c-'a']->fin = 0; } curr->num[c-'a']++; curr = curr->next[c - 'a']; } curr->fin++; } long long count(int kdx, string rule){ long long ret = 0; for(int i = 0; i < 26; i++){ for(int j = i + 1; j < 26; j++){ int ch1 = rule[i] - 'a'; int ch2 = rule[j] - 'a'; ret += memo[kdx][ch1][ch2]; } } return ret + memo[kdx][0][0] + 1; } void create_table(int idx){ node *curr = root; for (char c : S[idx] ) { long long tmp = 0; for(int i = 0; i < 26; i++){ if(i != c - 'a'){ memo[idx][i][c-'a'] += curr->num[i]; } } memo[idx][0][0] += curr->fin; curr = curr->next[c - 'a']; } } int main(){ cin >> N; //400000 for(int i = 0; i < N; i++){ cin >> S[i]; add(S[i]); } for(int i = 0; i < N; i++){ create_table(i); } long long Q; cin >> Q; for(int i = 0; i < Q; i++){ cin >> k[i] >> rules[i]; k[i]--; } /* for(int i = 0; i < N; i++){ cout << "i=" << i << endl; for(int j = 0; j < 26; j++){ for(int k = 0; k < 26; k++){ cout << "memo[" << i << "][" << (char)('a' + j) << "][" << (char)('a' + k) << "]=" << memo[i][j][k] << endl; } } } */ //1e5 for(int i = 0; i < Q; i++){ cout << count(k[i], rules[i]) << endl; } }
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | motomuman |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 2082 Byte |
Status | AC |
Exec Time | 1147 ms |
Memory | 318080 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 | 1147 ms | 312316 KB |
02.txt | AC | 1136 ms | 312192 KB |
03.txt | AC | 1136 ms | 312192 KB |
04.txt | AC | 1140 ms | 312192 KB |
05.txt | AC | 1026 ms | 215424 KB |
06.txt | AC | 902 ms | 150400 KB |
07.txt | AC | 879 ms | 144384 KB |
08.txt | AC | 878 ms | 142464 KB |
09.txt | AC | 865 ms | 142208 KB |
10.txt | AC | 859 ms | 141824 KB |
11.txt | AC | 881 ms | 101632 KB |
12.txt | AC | 947 ms | 142720 KB |
13.txt | AC | 988 ms | 188928 KB |
14.txt | AC | 890 ms | 144256 KB |
15.txt | AC | 869 ms | 142208 KB |
16.txt | AC | 856 ms | 141824 KB |
17.txt | AC | 871 ms | 141820 KB |
18.txt | AC | 713 ms | 13568 KB |
19.txt | AC | 726 ms | 13568 KB |
20.txt | AC | 724 ms | 13952 KB |
21.txt | AC | 718 ms | 13952 KB |
22.txt | AC | 724 ms | 13952 KB |
23.txt | AC | 937 ms | 137216 KB |
24.txt | AC | 896 ms | 100608 KB |
25.txt | AC | 934 ms | 141696 KB |
26.txt | AC | 714 ms | 13696 KB |
27.txt | AC | 748 ms | 34304 KB |
28.txt | AC | 761 ms | 43904 KB |
29.txt | AC | 735 ms | 30080 KB |
30.txt | AC | 867 ms | 87936 KB |
31.txt | AC | 791 ms | 54272 KB |
32.txt | AC | 742 ms | 38016 KB |
33.txt | AC | 760 ms | 56576 KB |
34.txt | AC | 768 ms | 50176 KB |
35.txt | AC | 766 ms | 63360 KB |
36.txt | AC | 1143 ms | 318080 KB |
37.txt | AC | 789 ms | 76224 KB |
38.txt | AC | 800 ms | 76224 KB |
39.txt | AC | 5 ms | 1792 KB |
40.txt | AC | 4 ms | 1792 KB |
s1.txt | AC | 4 ms | 1792 KB |
s2.txt | AC | 4 ms | 1792 KB |