oj.uz

Submission #1038929

# Submission time Handle Problem Language Result Execution time Memory
1038929 2024-07-30T09:30:20 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 216 ms 194004 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
struct tri
{
    struct node
    {
        vector<ll> cnt; ll child[4];
        node() {for (ll i = 0; i < 4; i++) child[i] = 0;}
    };
    vector<node> trie = {node()};
    void add(string& x, ll id)
    {
        ll u = 0;
        for (ll i = 0; i < x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) {trie.pb(node()); trie[u].child[x[i]-'A'] = trie.size()-1;}
            trie[u].cnt.pb(id); u = trie[u].child[x[i]-'A'];
        }
        trie[u].cnt.pb(id);
    } 
    ll get(string& x)
    {
        ll u = 0;
        for (ll i = 0; i < (ll)x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) return -1;
            u = trie[u].child[x[i]-'A'];
        }
        return u;
    }
    ll qget(string& x, ll l, ll r)
    {
        ll u = 0;
        for (ll i = 0; i < (ll)x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) return 0;
            u = trie[u].child[x[i]-'A'];
        }
        return upper_bound(trie[u].cnt.begin(),trie[u].cnt.end(),r)-lower_bound(trie[u].cnt.begin(),trie[u].cnt.end(),l);
    }
} tri1, tri2;
char trans(char x) 
{
    if (x == 'A') return 'A';
    if (x == 'U') return 'B';
    if (x == 'G') return 'C';
    return 'D';
}
ll n, m;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    vector<string> ss(n+1);
    for (ll i = 1; i <= n; i++) cin >> ss[i];
    sort(ss.begin(),ss.end());
    for (ll i = 1; i <= n; i++) 
    {
        string s = ss[i];
        for (char& j : s) j = trans(j); 
        tri1.add(s,i);
        reverse(s.begin(),s.end());
        tri2.add(s,i);
    }
    for (ll i = 1; i <= m; i++)
    {
        string a, b; cin >> a >> b;
        for (char& j : a) j = trans(j);
        for (char& j : b) j = trans(j);
        reverse(b.begin(),b.end());
        ll id = tri1.get(a);
        if (id == -1) {cout << 0 << '\n'; continue;}
        ll l = tri1.trie[id].cnt.front(), r = tri1.trie[id].cnt.back();
        cout << tri2.qget(b,l,r) << '\n';
    }
}

Compilation message

selling_rna.cpp: In member function 'void tri::add(std::string&, ll)':
selling_rna.cpp:21:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (ll i = 0; i < x.size(); i++)
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 156656 KB Output is correct
2 Correct 174 ms 148576 KB Output is correct
3 Correct 154 ms 154312 KB Output is correct
4 Correct 147 ms 147156 KB Output is correct
5 Correct 216 ms 192724 KB Output is correct
6 Correct 213 ms 194004 KB Output is correct
7 Correct 47 ms 24548 KB Output is correct
8 Correct 192 ms 132032 KB Output is correct
9 Correct 179 ms 115416 KB Output is correct
10 Correct 124 ms 111968 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4340 KB Output is correct
2 Correct 13 ms 3252 KB Output is correct
3 Correct 16 ms 3872 KB Output is correct
4 Correct 19 ms 3412 KB Output is correct
5 Correct 14 ms 3404 KB Output is correct
6 Correct 18 ms 3668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 173 ms 156656 KB Output is correct
9 Correct 174 ms 148576 KB Output is correct
10 Correct 154 ms 154312 KB Output is correct
11 Correct 147 ms 147156 KB Output is correct
12 Correct 216 ms 192724 KB Output is correct
13 Correct 213 ms 194004 KB Output is correct
14 Correct 47 ms 24548 KB Output is correct
15 Correct 192 ms 132032 KB Output is correct
16 Correct 179 ms 115416 KB Output is correct
17 Correct 124 ms 111968 KB Output is correct
18 Correct 17 ms 4340 KB Output is correct
19 Correct 13 ms 3252 KB Output is correct
20 Correct 16 ms 3872 KB Output is correct
21 Correct 19 ms 3412 KB Output is correct
22 Correct 14 ms 3404 KB Output is correct
23 Correct 18 ms 3668 KB Output is correct
24 Correct 168 ms 130580 KB Output is correct
25 Correct 175 ms 130964 KB Output is correct
26 Correct 173 ms 129168 KB Output is correct
27 Correct 154 ms 128856 KB Output is correct
28 Correct 130 ms 45404 KB Output is correct
29 Correct 61 ms 17608 KB Output is correct