oj.uz

Submission #1041058

# Submission time Handle Problem Language Result Execution time Memory
1041058 2024-08-01T14:31:19 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 127 ms 150332 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define ull unsigned long long
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sqr(x) sqrtl(x)
#define cbr(x) cbrtl(x)
#define sz(a) (ll)(a.size())
using namespace std;

const ld PI = acos(-1); const ll INFL = 2e18 + 7; const int INFI = 1e9 + 7;

int n, q, trie[2][2000005][4], node[2], l[2000005], r[2000005];
string x, y, s[100005];
vector <int> pos[2000005];

void add_string(string s, int id)
{
    for (int j = 0; j <= 1; j++)
    {
        int cur = 0;
        for (char i : s)
        {
            int temp;
            if (i == 'A') temp = 0;
            else if (i == 'C') temp = 1;
            else if (i == 'G') temp = 2;
            else temp = 3;
            if (!trie[j][cur][temp]) trie[j][cur][temp] = ++node[j];
            cur = trie[j][cur][temp];
            if (j == 0)
            {
                if (!l[cur]) l[cur] = id;
                r[cur] = id;
            }
            else pos[cur].pub(id);
        }
        reverse(s.begin(), s.end());
    }
}

int find_string(string x, string y)
{
    int cur = 0;
    for (char i : x)
    {
        int temp;
        if (i == 'A') temp = 0;
        else if (i == 'C') temp = 1;
        else if (i == 'G') temp = 2;
        else temp = 3;
        if (!trie[0][cur][temp]) return(0);
        cur = trie[0][cur][temp];
    }
    int L = l[cur], R = r[cur];
    cur = 0;
    for (char i : y)
    {
        int temp;
        if (i == 'A') temp = 0;
        else if (i == 'C') temp = 1;
        else if (i == 'G') temp = 2;
        else temp = 3;
        if (!trie[1][cur][temp]) return(0);
        cur = trie[1][cur][temp];
    }
    return(upper_bound(pos[cur].begin(), pos[cur].end(), R) - lower_bound(pos[cur].begin(), pos[cur].end(), L));
}

void Solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) add_string(s[i], i);
    while (q--)
    {
        cin >> x >> y;
        cout << find_string(x, y) << el;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(0);
    
    Solve();
    return 0;
}

//coded by icyalmond

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 51804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 150332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 53072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 51804 KB Output isn't correct
2 Halted 0 ms 0 KB -