oj.uz

Submission #1041110

# Submission time Handle Problem Language Result Execution time Memory
1041110 2024-08-01T15:48:13 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 127 ms 146256 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];

int get_char(char x)
{
    if (x == 'A') return(0);
    else if (x == 'C') return(1);
    else if (x == 'G') return(2);
    else return(3);
}

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

int find_string(string x, string y)
{
    int cur = 0;
    for (char i : x)
    {
        if (!trie[0][cur][get_char(i)]) return(0);
        cur = trie[0][cur][get_char(i)];
    }
    int L = l[cur], R = r[cur];
    cur = 0;
    reverse(y.begin(), y.end());
    for (char i : y)
    {
        if (!trie[1][cur][get_char(i)]) return(0);
        cur = trie[1][cur][get_char(i)];
    }
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51804 KB Output is correct
2 Correct 8 ms 51804 KB Output is correct
3 Correct 8 ms 51852 KB Output is correct
4 Correct 8 ms 51800 KB Output is correct
5 Correct 7 ms 51908 KB Output is correct
6 Correct 8 ms 52060 KB Output is correct
7 Correct 8 ms 51804 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 146256 KB Output is correct
2 Correct 104 ms 145488 KB Output is correct
3 Correct 52 ms 113744 KB Output is correct
4 Correct 57 ms 111188 KB Output is correct
5 Correct 93 ms 140884 KB Output is correct
6 Correct 92 ms 141904 KB Output is correct
7 Correct 36 ms 67408 KB Output is correct
8 Correct 88 ms 115148 KB Output is correct
9 Correct 79 ms 107272 KB Output is correct
10 Correct 63 ms 103708 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 52828 KB Output is correct
2 Correct 19 ms 53084 KB Output is correct
3 Correct 22 ms 53072 KB Output is correct
4 Correct 17 ms 52820 KB Output is correct
5 Correct 19 ms 53084 KB Output is correct
6 Correct 20 ms 53076 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51804 KB Output is correct
2 Correct 8 ms 51804 KB Output is correct
3 Correct 8 ms 51852 KB Output is correct
4 Correct 8 ms 51800 KB Output is correct
5 Correct 7 ms 51908 KB Output is correct
6 Correct 8 ms 52060 KB Output is correct
7 Correct 8 ms 51804 KB Output is correct
8 Correct 120 ms 146256 KB Output is correct
9 Correct 104 ms 145488 KB Output is correct
10 Correct 52 ms 113744 KB Output is correct
11 Correct 57 ms 111188 KB Output is correct
12 Correct 93 ms 140884 KB Output is correct
13 Correct 92 ms 141904 KB Output is correct
14 Correct 36 ms 67408 KB Output is correct
15 Correct 88 ms 115148 KB Output is correct
16 Correct 79 ms 107272 KB Output is correct
17 Correct 63 ms 103708 KB Output is correct
18 Correct 20 ms 52828 KB Output is correct
19 Correct 19 ms 53084 KB Output is correct
20 Correct 22 ms 53072 KB Output is correct
21 Correct 17 ms 52820 KB Output is correct
22 Correct 19 ms 53084 KB Output is correct
23 Correct 20 ms 53076 KB Output is correct
24 Correct 105 ms 133716 KB Output is correct
25 Correct 127 ms 133896 KB Output is correct
26 Correct 116 ms 132764 KB Output is correct
27 Correct 58 ms 105680 KB Output is correct
28 Correct 106 ms 77392 KB Output is correct
29 Correct 48 ms 60328 KB Output is correct