fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ld long double
  8. #define ll long long
  9. #define pb push_back
  10. #define fin(a, n) for(int i = a; i < n; i++)
  11. #define fjn(a, n) for(int j = a; j < n; j++)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a) a.rbegin(),a.rend()
  14. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  15.  
  16. using namespace std;
  17.  
  18. const double PI = acos(-1);
  19. const int N = 2e6+10, M = 1e3+10;
  20. const ll oo = 0x3f3f3f3f3f3f3f3f;
  21. const int mod = 1e9+7, inf = 1e6;
  22. const ld EPS = 1e-9;
  23.  
  24. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  25. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  26. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  27. char dc[] = {'D', 'L', 'R', 'U'};
  28.  
  29. vector<int> mp, mp2;
  30. struct node {
  31.     node *nxt[10];
  32.     int cnt, end;
  33.  
  34.     node() {
  35.         cnt = 0, end = 0;
  36.         memset(nxt, 0, sizeof nxt);
  37.     }
  38. };
  39.  
  40. struct Trie {
  41.     node *root;
  42.  
  43.     Trie() {
  44.         root = new node();
  45.     }
  46.  
  47.     void insert(string s) {
  48.         node *cur = root;
  49.         for (int i = 0; i < s.size(); i++) {
  50.             if (!cur->nxt[s[i]-'0']) cur->nxt[s[i]-'0'] = new node();
  51.             cur->cnt++;
  52.             cur = cur->nxt[s[i]-'0'];
  53.         }
  54.         cur->cnt++;
  55.         cur->end++;
  56.     }
  57.  
  58.     ll query(string s) {
  59.         node *cur = root;
  60.         ll ret = 0;
  61.         bool lz = true;
  62.         for (int i = 0; i < s.size(); i++) {
  63.             if (lz && s[i]-'0' > 0) lz = false;
  64.             if (!cur->nxt[s[i] - '0'] || cur->nxt[s[i] - '0']->cnt == 0) return 0;
  65.             if (!lz){
  66.                 for (int x = mp[s[i]-'0']-1; x >= 0; x--) {
  67.                     if (!cur->nxt[mp2[x]] || cur->nxt[mp2[x]]->cnt == 0)continue;
  68.                     ret += cur->nxt[mp2[x]]->cnt;
  69.                 }
  70.             }
  71.             cur = cur->nxt[s[i] - '0'];
  72.         }
  73.         return ret;
  74.     }
  75. };
  76.  
  77. void solve() {
  78.     mp.assign(10, 0);
  79.     mp2.assign(10, 0);
  80.     ll n; cin >> n;
  81.     vector<string> v(n);
  82.     fin(0, n) {
  83.         cin >> v[i];
  84.         v[i] = string(19-v[i].size(), '0') + v[i];
  85.     }
  86.     Trie tr;
  87.     fin(0, n) tr.insert(v[i]);
  88.     ll q; cin >> q;
  89.     while (q--) {
  90.         fin(0, 10) {
  91.             int x; cin >> x;
  92.             mp[x] = i;
  93.             mp2[i] = x;
  94.         }
  95.         string x; cin  >> x;
  96.         x = string(19-x.size(), '0')+x;
  97.         cout << tr.query(x) << "\n";
  98.     }
  99. }
  100.  
  101. int main() {
  102.     FAST;
  103. #ifndef ONLINE_JUDGE
  104.     freopen("input.txt","r",stdin);
  105.     freopen("output.txt","w",stdout);
  106. #endif
  107.     int tt = 1; //cin >> tt;
  108.     while(tt--){
  109.         solve();
  110.     }
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7ll6BP
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!