//shikanokonokonokokoshitantan
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const bool typetest = 0;
const ll N = 2e5 + 5;
#define inf LLONG_MAX/2
#define bit(x,y) ((x >> y) & 1)
ll sech[N][30];
ll get(ll l, ll r)
{
ll cnt = 0;
ll tmp = 1;
while(tmp * 2 <= r - l)
{
tmp *= 2;
cnt++;
}
return min(sech[l + 1][cnt],sech[r - tmp + 1][cnt]);
}
struct node
{
node* c[26];
vector<ll> v;
node()
{
for(ll i = 0;i < 26;i++) c[i] = NULL;
}
};
string a[N];
struct trie
{
node root;
void add(string s, ll t)
{
ll i = 0;
node *cur = &root;
while(i < s.size())
{
ll k = s[i] - 'A';
if(!cur->c[k])
{
cur->c[k] = new node();
}
cur = cur->c[k];
cur->v.push_back(t);
i++;
}
}
ll cal(string x, string s)
{
ll i = 0;
node *cur = &root;
ll ans = 0;
while(i < s.size())
{
ll k = s[i] - 'A';
if(!cur->c[k])
{
return 0;
}
cur = cur->c[k];
i++;
}
ll l = 0, r = cur->v.size() - 1;
ll k = 0;
while(true)
{
if(l == r)
{
k = l;
break;
}
if(l + 1 == r)
{
if(a[cur->v[l]] >= x) k = l;
else k = r;
break;
}
ll mid = (l + r) / 2;
if(a[cur->v[mid]] >= x) r = mid;
else l = mid;
}
for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
if(i >= x.size())
{
ll k1;
l = 0,r = k;
while(true)
{
if(l == r)
{
k1 = l;
break;
}
if(l + 1 == r)
{
if(get(l,k) >= x.size()) k1 = l;
else k1 = r;
break;
}
ll mid = (l + r) / 2;
if(get(mid,k) >= x.size()) r = mid;
else l = mid;
}
ll k2;
l = k,r = cur->v.size() - 1;
while(true)
{
if(l == r)
{
k2 = l;
break;
}
if(l + 1 == r)
{
if(get(cur->v[k],cur->v[r]) >= x.size()) k2 = r;
else k2 = l;
break;
}
ll mid = (l + r) / 2;
if(get(cur->v[k],cur->v[mid]) >= x.size()) l = mid;
else r = mid;
}
return k2 - k1 + 1;
}else return 0;
}
};
trie f;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n,q;
cin >> n >> q;
ll i,j;
for(i = 1;i <= n;i++) cin >> a[i];
sort(a + 1,a + 1 + n);
for(i = 2;i <= n;i++)
{
for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
{
if(a[i][j] == a[i - 1][j]) sech[i][0]++;
else break;
}
}
for(i = 1;i <= 20;i++)
{
for(j = 2;j + (1 << (i - 1)) <= n;j++)
{
sech[j][i] = min(sech[j][i - 1],sech[j + (1 << (i - 1))][i - 1]);
}
}
for(i = 1;i <= n;i++)
{
reverse(a[i].begin(),a[i].end());
f.add(a[i],i);
reverse(a[i].begin(),a[i].end());
}
while(q--)
{
string pre= "";
string suf= "";
cin >> pre >> suf;
reverse(suf.begin(),suf.end());
cout << f.cal(pre,suf) << "\n";
}
}
Compilation message
selling_rna.cpp: In member function 'void trie::add(std::string, ll)':
selling_rna.cpp:43:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | while(i < s.size())
| ~~^~~~~~~~~~
selling_rna.cpp: In member function 'll trie::cal(std::string, std::string)':
selling_rna.cpp:61:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while(i < s.size())
| ~~^~~~~~~~~~
selling_rna.cpp:90:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
| ~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:90:48: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(i = 0;i < a[cur->v[k]].size() && i < x.size() && a[cur->v[k]][i] == x[i];i++);
| ~~^~~~~~~~~~
selling_rna.cpp:91:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(i >= x.size())
| ~~^~~~~~~~~~~
selling_rna.cpp:104:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | if(get(l,k) >= x.size()) k1 = l;
| ~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:109:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if(get(mid,k) >= x.size()) r = mid;
| ~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:123:49: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if(get(cur->v[k],cur->v[r]) >= x.size()) k2 = r;
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:128:47: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | if(get(cur->v[k],cur->v[mid]) >= x.size()) l = mid;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
selling_rna.cpp:60:12: warning: unused variable 'ans' [-Wunused-variable]
60 | ll ans = 0;
| ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:148:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
| ~~^~~~~~~~~~~~~
selling_rna.cpp:148:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(j = 0;j < a[i].size() && j < a[i - 1].size();j++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
302 ms |
537076 KB |
Output is correct |
| 2 |
Incorrect |
292 ms |
509072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
20816 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
17496 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
