oj.uz

Submission #691780

# Submission time Handle Problem Language Result Execution time Memory
691780 2023-01-31T14:22:32 Z danikoynov Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 663 ms 710828 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, alphabet = 26;

int n, m;
string rna[maxn];

struct query
{
    string p, q;
}ask[maxn];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> rna[i];
    for (int i = 1; i <= m; i ++)
        cin >> ask[i].p >> ask[i].q;
    sort(rna + 1, rna + n + 1);
}

struct trie
{
    trie *child[alphabet];
    int left, right;
    vector < int > bucket;

    trie()
    {
        for (int i = 0; i < alphabet; i ++)
            child[i] = NULL;
        left = 1e9;
        right = 0;
    }
};

void add(trie *root, string &word, int pos, int idx)
{
     root -> left = min(root -> left, idx);
    root -> right = max(root -> right, idx);
    root -> bucket.push_back(idx);
    if (pos == word.size())
        return;

    int go = word[pos] - 'A';
    if (root -> child[go] == NULL)
        root -> child[go] = new trie();

    add(root -> child[go], word, pos + 1, idx);
}

trie *ft = new trie(), *bk = new trie();

void build_trie()
{
    for (int i = 1; i <= n; i ++)
    {
        add(ft, rna[i], 0, i);
        reverse(rna[i].begin(), rna[i].end());
        add(bk, rna[i], 0, i);
    }
}

pair < int, int > query_range(trie *root, string &word, int pos)
{
    if (pos == word.size())
    return make_pair(root -> left, root -> right);

    int go = word[pos] - 'A';
    if (root -> child[go] == NULL)
        return make_pair(1e9, 0);

    return query_range(root -> child[go], word, pos + 1);
}

int calculate(vector < int > &bucket, pair < int, int > range)
{
    int lf = 0, rf = (int)(bucket.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (bucket[mf] < range.first)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    int f1 = lf;

    lf = 0;
    rf = (int)(bucket.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (bucket[mf] <= range.second)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    int f2 = rf;

    return max(0, f2 - f1 + 1);
}

int query(trie *root, string &word, int pos, pair < int, int > &range)
{
    if (pos == word.size())
    {
        return calculate(root -> bucket, range);
    }

    int go = word[pos] - 'A';
    ///cout << go << endl;
    if (root -> child[go] == NULL)
        return 0;

    return query(root -> child[go], word, pos + 1, range);

}
void solve_queries()
{
    for (int i = 1; i <= m; i ++)
    {
        pair < int, int > range = query_range(ft, ask[i].p, 0);
        reverse(ask[i].q.begin(), ask[i].q.end());
        int ans = query(bk, ask[i].q, 0, range);
        ///cout << range.first << " " << range.second << endl;
        cout << ans << endl;
    }
}

void solve()
{
    input();
    build_trie();
    solve_queries();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void add(trie*, std::string&, int, int)':
selling_rna.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if (pos == word.size())
      |         ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> query_range(trie*, std::string&, int)':
selling_rna.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     if (pos == word.size())
      |         ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(trie*, std::string&, int, std::pair<int, int>&)':
selling_rna.cpp:120:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     if (pos == word.size())
      |         ~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9688 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 35 ms 9676 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 580900 KB Output is correct
2 Correct 404 ms 552140 KB Output is correct
3 Correct 386 ms 576284 KB Output is correct
4 Correct 366 ms 549172 KB Output is correct
5 Correct 663 ms 700484 KB Output is correct
6 Correct 499 ms 710828 KB Output is correct
7 Correct 132 ms 38636 KB Output is correct
8 Correct 394 ms 436148 KB Output is correct
9 Correct 326 ms 369760 KB Output is correct
10 Correct 254 ms 355464 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11592 KB Output is correct
2 Correct 23 ms 12800 KB Output is correct
3 Correct 30 ms 12320 KB Output is correct
4 Correct 21 ms 11504 KB Output is correct
5 Correct 25 ms 12740 KB Output is correct
6 Correct 28 ms 12264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 9 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9688 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 35 ms 9676 KB Output is correct
8 Correct 436 ms 580900 KB Output is correct
9 Correct 404 ms 552140 KB Output is correct
10 Correct 386 ms 576284 KB Output is correct
11 Correct 366 ms 549172 KB Output is correct
12 Correct 663 ms 700484 KB Output is correct
13 Correct 499 ms 710828 KB Output is correct
14 Correct 132 ms 38636 KB Output is correct
15 Correct 394 ms 436148 KB Output is correct
16 Correct 326 ms 369760 KB Output is correct
17 Correct 254 ms 355464 KB Output is correct
18 Correct 26 ms 11592 KB Output is correct
19 Correct 23 ms 12800 KB Output is correct
20 Correct 30 ms 12320 KB Output is correct
21 Correct 21 ms 11504 KB Output is correct
22 Correct 25 ms 12740 KB Output is correct
23 Correct 28 ms 12264 KB Output is correct
24 Correct 519 ms 481228 KB Output is correct
25 Correct 408 ms 481532 KB Output is correct
26 Correct 397 ms 475532 KB Output is correct
27 Correct 361 ms 475088 KB Output is correct
28 Correct 196 ms 96164 KB Output is correct
29 Correct 80 ms 23728 KB Output is correct