oj.uz

Submission #1069831

# Submission time Handle Problem Language Result Execution time Memory
1069831 2024-08-22T09:17:02 Z cpismylifeOwO Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 184 ms 199248 KB 
#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int BlockSize = 317;
const int MaxTrie = 2e6 + 5;

struct Que
{
    int l, r, id;

    Que() = default;

    Que(int _l, int _r, int _id)
    {
        l = _l;
        r = _r;
        id = _id;
    }
};

int n, m;
string arr[MaxN];
string pre[MaxN];
string suf[MaxN];

void Inp()
{
    cin >> n >> m;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
    for (int x = 1; x <= m; x++)
    {
        cin >> pre[x] >> suf[x];
    }
    sort(arr + 1, arr + n + 1);
}

struct Node
{
    int child[4];
    int exist, cnt, l, r;
    vector<int> contain;

    Node()
    {
        child[0] =  child[1] = child[2] = child[3] = -1;
        exist = cnt = 0;
        l = n + 1;
        r = 0;
        contain.clear();
    }
};

int curPos;
Node Trie[MaxTrie];
int res[MaxN];

int Cov(char a)
{
    if (a == 'C')
    {
        return 0;
    }
    if (a == 'U')
    {
        return 1;
    }
    if (a == 'G')
    {
        return 2;
    }
    return 3;
}

void Add(string s, int p)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            curPos++;
            Trie[curPos] = Node();
            Trie[pos].child[c] = curPos;
        }
        pos = Trie[pos].child[c];
        Trie[pos].l = min(Trie[pos].l, p);
        Trie[pos].r = max(Trie[pos].r, p);
        Trie[pos].contain.push_back(p);
        Trie[pos].cnt++;
    }
    Trie[pos].exist++;
}

pair<int, int> GetPlace(string s)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            return make_pair(-1, -1);
        }
        pos = Trie[pos].child[c];
    }
    return make_pair(Trie[pos].l, Trie[pos].r);
}

int BSearch(int pos, int k)
{
    int l = 0, r = (int)Trie[pos].contain.size() - 1, mid, res = -1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (Trie[pos].contain[mid] <= k)
        {
            res = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return res + 1;
}

int Count(string s, int l, int r)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            return 0;
        }
        pos = Trie[pos].child[c];
    }
    return BSearch(pos, r) - BSearch(pos, l - 1);
}

vector<Que> query;

void Exc()
{
    curPos = 0;
    Trie[0] = Node();
    Trie[0].l = 1;
    Trie[0].r = n;
    for (int x = 1; x <= n; x++)
    {
        Add(arr[x], x);
    }
    for (int x = 1; x <= m; x++)
    {
        pair<int, int> p = GetPlace(pre[x]);
        if (p.first != -1)
        {
            query.push_back(Que(p.first, p.second, x));
        }
        else
        {
            res[x] = 0;
        }
        //cout << pre[x] << " " << p.first << " " << p.second << "\n";
    }
    curPos = 0;
    Trie[0] = Node();
    for (int x = 1; x <= n; x++)
    {
        reverse(arr[x].begin(), arr[x].end());
        //cout << arr[x] << " ";
        Add(arr[x], x);
    }
    for (Que& x : query)
    {
        reverse(suf[x.id].begin(), suf[x.id].end());
        //cout << suf[x.id] << " ";
        res[x.id] = Count(suf[x.id], x.l, x.r);
    }
    for (int x = 1; x <= m; x++)
    {
        cout << res[x] << "\n";
    }
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 119644 KB Output is correct
2 Correct 18 ms 119644 KB Output is correct
3 Correct 23 ms 119640 KB Output is correct
4 Correct 26 ms 119668 KB Output is correct
5 Correct 18 ms 119644 KB Output is correct
6 Correct 24 ms 119640 KB Output is correct
7 Correct 23 ms 119636 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 185172 KB Output is correct
2 Correct 170 ms 185976 KB Output is correct
3 Correct 169 ms 199248 KB Output is correct
4 Correct 171 ms 195952 KB Output is correct
5 Correct 172 ms 163164 KB Output is correct
6 Correct 175 ms 163704 KB Output is correct
7 Correct 65 ms 139348 KB Output is correct
8 Correct 172 ms 160500 KB Output is correct
9 Correct 131 ms 156272 KB Output is correct
10 Correct 108 ms 151808 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 121464 KB Output is correct
2 Correct 34 ms 120888 KB Output is correct
3 Correct 52 ms 121396 KB Output is correct
4 Correct 35 ms 121480 KB Output is correct
5 Correct 35 ms 121680 KB Output is correct
6 Correct 52 ms 121808 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 119644 KB Output is correct
2 Correct 18 ms 119644 KB Output is correct
3 Correct 23 ms 119640 KB Output is correct
4 Correct 26 ms 119668 KB Output is correct
5 Correct 18 ms 119644 KB Output is correct
6 Correct 24 ms 119640 KB Output is correct
7 Correct 23 ms 119636 KB Output is correct
8 Correct 180 ms 185172 KB Output is correct
9 Correct 170 ms 185976 KB Output is correct
10 Correct 169 ms 199248 KB Output is correct
11 Correct 171 ms 195952 KB Output is correct
12 Correct 172 ms 163164 KB Output is correct
13 Correct 175 ms 163704 KB Output is correct
14 Correct 65 ms 139348 KB Output is correct
15 Correct 172 ms 160500 KB Output is correct
16 Correct 131 ms 156272 KB Output is correct
17 Correct 108 ms 151808 KB Output is correct
18 Correct 40 ms 121464 KB Output is correct
19 Correct 34 ms 120888 KB Output is correct
20 Correct 52 ms 121396 KB Output is correct
21 Correct 35 ms 121480 KB Output is correct
22 Correct 35 ms 121680 KB Output is correct
23 Correct 52 ms 121808 KB Output is correct
24 Correct 184 ms 178744 KB Output is correct
25 Correct 161 ms 179900 KB Output is correct
26 Correct 164 ms 177820 KB Output is correct
27 Correct 167 ms 188432 KB Output is correct
28 Correct 166 ms 145852 KB Output is correct
29 Correct 99 ms 130112 KB Output is correct