#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
map <char, ll> Map;
ll tin[2][200005], tout[2][200005];
ll k, ans[200005];
struct Node
{
vector <ll> crr;
ll child[4];
Node ()
{
fill(begin(child), end(child), -1);
}
};
struct Trie
{
ll Time=0;
vector <Node> t;
Trie ()
{
t.emplace_back();
}
void addstring(string s, ll idx)
{
ll p=0;
for (ll i=0; i<s.size(); i++)
{
ll c=Map[s[i]];
if (t[p].child[c]==-1)
{
t[p].child[c]=t.size();
t.emplace_back();
}
p=t[p].child[c];
}
t[p].crr.pb(idx);
}
void setup(ll p, ll num)
{
Time++;
for (ll i:t[p].crr)
tin[num][i]=Time;
for (ll i=0; i<4; i++)
if (t[p].child[i]!=-1)
setup(t[p].child[i], num);
for (ll i:t[p].crr)
tout[num][i]=Time;
k=max(k, Time);
}
};
vector <ll> num[200005];
vector <pair<pll, pll>> event[200005];
struct BIT
{
ll n;
vector <ll> bit;
BIT (ll n): n(n)
{
bit.assign(n+5, 0);
}
void update(ll i, ll val)
{
for (i; i<=n; i+=i&(-i))
bit[i]+=val;
}
ll query(ll l, ll r)
{
ll ans=0; l--;
for (r; r>0; r-=r&(-r))
ans+=bit[r];
for (l; l>0; l-=l&(-l))
ans-=bit[l];
return ans;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
Map['A']=0; Map['G']=1; Map['C']=2; Map['U']=3;
ll n, m; cin >> n >> m;
Trie A1, A2;
for (ll i=1; i<=n; i++)
{
string s; cin >> s;
A1.addstring(s, i);
reverse(s.begin(), s.end());
A2.addstring(s, i);
}
for (ll i=1; i<=m; i++)
{
string p, s; cin >> p >> s;
reverse(s.begin(), s.end());
A1.addstring(p, i+n);
A2.addstring(s, i+n);
}
A1.setup(0, 0); A2.setup(0, 1);
for (ll i=1; i<=m; i++)
{
event[tin[0][i+n]-1].pb({{tin[1][i+n], tout[1][i+n]}, {i, -1}});
event[tout[0][i+n]].pb({{tin[1][i+n], tout[1][i+n]}, {i, 1}});
}
for (ll i=1; i<=n; i++)
num[tin[0][i]].pb(tin[1][i]);
BIT A(k);
for (ll i=0; i<=k; i++)
{
for (ll j:num[i])
A.update(j, 1);
for (pair<pll, pll> j:event[i])
{
ll l=j.fi.fi, r=j.fi.se, idx=j.se.fi, mul=j.se.se;
ans[idx]+=A.query(l, r)*mul;
}
}
for (ll i=1; i<=m; i++)
cout << ans[i] << " ";
}
Compilation message
selling_rna.cpp: In member function 'void Trie::addstring(std::string, long long int)':
selling_rna.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (ll i=0; i<s.size(); i++)
| ~^~~~~~~~~
selling_rna.cpp: In member function 'void BIT::update(long long int, long long int)':
selling_rna.cpp:81:14: warning: statement has no effect [-Wunused-value]
81 | for (i; i<=n; i+=i&(-i))
| ^
selling_rna.cpp: In member function 'long long int BIT::query(long long int, long long int)':
selling_rna.cpp:88:14: warning: statement has no effect [-Wunused-value]
88 | for (r; r>0; r-=r&(-r))
| ^
selling_rna.cpp:90:14: warning: statement has no effect [-Wunused-value]
90 | for (l; l>0; l-=l&(-l))
| ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
