| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 361765 | RyoPham | Selling RNA Strands (JOI16_selling_rna) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define taskname "test"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define fi first
#define se second
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
int n, m;
string s[maxn], t[maxn];
int id_s[maxn], id_t[maxn];
string q_pref[maxn], q_suff[maxn];
int q_pref_id[maxn], q_suff_id[maxn];
int nnode[2];
int gr[2][maxn][4];
int ntime;
int tin[2][maxn], tout[2][maxn];
struct fenwick
{
vector<int> vals[maxn], sum[maxn];
void fake_update(int x, int y)
{
for(; x < maxn; x += x & -x)
vals[x].push_back(y);
}
void fake_get(int x, int y)
{
for(; x > 0; x -= x & -x)
vals[x].push_back(y);
}
void fake_get(int xl, int yl, int xr, int yr)
{
fake_get(xr, yr);
fake_get(xl - 1, yr);
fake_get(xr, yl - 1);
fake_get(xl - 1, yl - 1);
}
void modify()
{
for(int x = 1; x < maxn; ++x)
{
sort(vals[x].begin(), vals[x].end());
vals[x].erase(unique(vals[x].begin(), vals[x].end()), vals[x].end());
sum[x].assign(sz(vals[x]) + 1, 0);
}
}
void update(int x, int yy)
{
for(; x < maxn; x += x & -x)
for(int y = lower_bound(vals[x].begin(), vals[x].end(), yy) - vals[x].begin() + 1; y <= sz(vals[x]); y += y & -y)
++sum[x][y];
}
int get(int x, int yy)
{
int res = 0;
for(; x > 0; x -= x & -x)
for(int y = lower_bound(vals[x].begin(), vals[x].end(), yy) - vals[x].begin() + 1; y > 0; y -= y & -y)
res += sum[x][y];
return res;
}
int get(int xl, int yl, int xr, int yr)
{
return get(xr, yr) - get(xl - 1, yr) - get(xr, yl - 1) + get(xl - 1, yl - 1);
}
} tree;
int get_type(char c)
{
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
if(c == 'U') return 3;
return -1;
}
void read_input()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> s[i];
t[i] = s[i];
reverse(t[i].begin(), t[i].end());
}
for(int i = 1; i <= m; ++i)
{
cin >> q_pref[i] >> q_suff[i];
reverse(q_suff[i].begin(), q_suff[i].end());
}
}
int add(int id, string s)
{
int cur = 1;
for(int i = 0; i < sz(s); ++i)
{
int nxt = gr[id][cur][get_type(s[i])];
if(nxt == 0)
nxt = gr[id][cur][get_type(s[i])] = ++nnode[id];
cur = nxt;
}
return cur;
}
int dfs_find(int id, string s)
{
int cur = 1;
for(int i = 0; i < sz(s); ++i)
{
int nxt = gr[id][cur][get_type(s[i])];
if(nxt == 0)
return 0;
cur = nxt;
}
return cur;
}
void dfs(int id, int u)
{
tin[id][u] = ++ntime;
for(int k = 0; k < 4; ++k)
if(gr[id][u][k]) dfs(id, gr[id][u][k]);
tout[id][u] = ntime;
}
void init()
{
nnode[0] = nnode[1] = 1;
for(int i = 1; i <= n; ++i)
{
id_s[i] = add(0, s[i]);
id_t[i] = add(1, t[i]);
}
for(int i = 1; i <= m; ++i)
{
q_pref_id[i] = dfs_find(0, q_pref[i]);
q_suff_id[i] = dfs_find(1, q_suff[i]);
}
for(int i = 0; i < 2; ++i)
{
ntime = 0;
dfs(i, 1);
}
for(int i = 1; i <= n; ++i)
tree.fake_update(tin[0][id_s[i]], tin[1][id_t[i]]);
for(int i = 1; i <= m; ++i)
if(q_pref_id[i] && q_suff_id[i])
tree.fake_get(tin[0][q_pref_id[i]], tin[1][q_suff_id[i]], tout[0][q_pref_id[i]], tout[1][q_suff_id[i]]);
tree.modify();
}
void solve()
{
for(int i = 1; i <= n; ++i)
tree.update(tin[0][id_s[i]], tin[1][id_t[i]]);
for(int i = 1; i <= m; ++i)
cout << (q_pref_id[i] && q_suff_id[i] ?
tree.get(tin[0][q_pref_id[i]], tin[1][q_suff_id[i]], tout[0][q_pref_id[i]], tout[1][q_suff_id[i]]) : 0) << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
init();
solve();
}