oj.uz

Submission #1081597

# Submission time Handle Problem Language Result Execution time Memory
1081597 2024-08-30T07:58:50 Z danglayloi1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 216 ms 148096 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const int nx=1e5+5;
const int N=2e6+5;
int getid(char c)
{
    if(c=='A')
        return 0;
    if(c=='C')
        return 1;
    if(c=='G')
        return 2;
    return 3;
}
int n, m;
string a[nx];
struct trie
{
    struct dak
    {
        int child[4], l, r;
        dak()
        {
            memset(child, -1, sizeof(child));
            l=inf, r=0;
        }
    };
    vector<dak> nod;
    trie()
    {
        nod.emplace_back();
    }
    void add(string s, int id)
    {
        int pos=0;
        for(int i = 0; i < s.size(); i++)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                nod[pos].child[c]=nod.size(), nod.emplace_back();
            pos=nod[pos].child[c];
            nod[pos].l=min(nod[pos].l, id);
            nod[pos].r=max(nod[pos].r, id);
        }
    }
    ii get_range(string s)
    {
        int pos=0;
        for(int i = 0; i < s.size(); i++)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                return ii(-1, -1);
            pos=nod[pos].child[c];
        }
        return ii(nod[pos].l, nod[pos].r);
    }
} T;
struct rev_trie
{
    struct dak
    {
        int child[4];
        vector<int> ids;
        dak()
        {
            memset(child, -1, sizeof(child));
            ids.clear();
        }
    };
    vector<dak> nod;
    rev_trie()
    {
        nod.emplace_back();
    }
    void add(string s, int id)
    {
        int pos=0;
        for(int i = s.size()-1; i >= 0; i--)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                nod[pos].child[c]=nod.size(), nod.emplace_back();
            pos=nod[pos].child[c];
            nod[pos].ids.emplace_back(id);
        }
    }
    int query(string s, ii f)
    {
        int pos=0;
        for(int i = s.size()-1; i >= 0; i--)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                return 0;
            pos=nod[pos].child[c];
        }
        int l=lower_bound(nod[pos].ids.begin(), nod[pos].ids.end(), f.fi)-nod[pos].ids.begin();
        int r=upper_bound(nod[pos].ids.begin(), nod[pos].ids.end(), f.se)-nod[pos].ids.begin();
        return r-l;
    }
} T1;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i++)
    {
        T.add(a[i], i);
        T1.add(a[i], i);
    }
    while(m--)
    {
        string x, y;
        cin>>x>>y;
        ii cur=T.get_range(x);
        cout<<T1.query(y, cur)<<'\n';
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3596 KB Output is correct
2 Correct 2 ms 3588 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 148096 KB Output is correct
2 Correct 216 ms 140656 KB Output is correct
3 Correct 105 ms 66708 KB Output is correct
4 Correct 77 ms 64192 KB Output is correct
5 Correct 164 ms 145840 KB Output is correct
6 Correct 161 ms 145856 KB Output is correct
7 Correct 38 ms 18932 KB Output is correct
8 Correct 132 ms 93956 KB Output is correct
9 Correct 110 ms 80772 KB Output is correct
10 Correct 92 ms 83132 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4824 KB Output is correct
2 Correct 14 ms 4792 KB Output is correct
3 Correct 16 ms 4880 KB Output is correct
4 Correct 13 ms 4444 KB Output is correct
5 Correct 14 ms 4732 KB Output is correct
6 Correct 17 ms 4700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3596 KB Output is correct
2 Correct 2 ms 3588 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 205 ms 148096 KB Output is correct
9 Correct 216 ms 140656 KB Output is correct
10 Correct 105 ms 66708 KB Output is correct
11 Correct 77 ms 64192 KB Output is correct
12 Correct 164 ms 145840 KB Output is correct
13 Correct 161 ms 145856 KB Output is correct
14 Correct 38 ms 18932 KB Output is correct
15 Correct 132 ms 93956 KB Output is correct
16 Correct 110 ms 80772 KB Output is correct
17 Correct 92 ms 83132 KB Output is correct
18 Correct 17 ms 4824 KB Output is correct
19 Correct 14 ms 4792 KB Output is correct
20 Correct 16 ms 4880 KB Output is correct
21 Correct 13 ms 4444 KB Output is correct
22 Correct 14 ms 4732 KB Output is correct
23 Correct 17 ms 4700 KB Output is correct
24 Correct 185 ms 123008 KB Output is correct
25 Correct 190 ms 123184 KB Output is correct
26 Correct 180 ms 122976 KB Output is correct
27 Correct 82 ms 64372 KB Output is correct
28 Correct 116 ms 33732 KB Output is correct
29 Correct 54 ms 12004 KB Output is correct