oj.uz

Submission #624370

# Submission time Handle Problem Language Result Execution time Memory
624370 2022-08-08T04:19:31 Z fdnfksd Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 331 ms 250316 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=2e5;
ll n,q,a[maxN];
struct TrieNode {
    TrieNode* child[4];
    vector<ll> pos;
    TrieNode() {
        for (int i=0; i<4; ++i)
            child[i]=NULL;
        pos.clear();
    }
};
ll val[300];
TrieNode *root=new TrieNode();
TrieNode *root1=new TrieNode();
#define pb push_back
void TrieInsert(const string &s, ll id)
{
    int nn=s.length();
    TrieNode* p=root;
    for (int i=0; i<nn; ++i) {
        int nxt=val[s[i]];
        if (p->child[nxt]==NULL)
            p->child[nxt]=new TrieNode();
        p=p->child[nxt];
        p->pos.pb(id);
    }
}
void add(const string &s, ll id)
{
    int nn=s.length();
    TrieNode* p=root1;
    for (int i=0; i<nn; ++i) {
        int nxt=val[s[i]];
        if (p->child[nxt]==NULL)
            p->child[nxt]=new TrieNode();
        p=p->child[nxt];
        p->pos.pb(id);
    }
}
bool cmp(string x, string y)
{
    reverse(x.begin(),x.end());
    reverse(y.begin(),y.end());
    for(int i=0;i<min(x.length(),y.length());i++)
    {
        if(x[i]<y[i]) return true;
        if(x[i]>y[i]) return false;
    }
    if(x.length()<y.length())return true;
    return false;
}

ll m;
string s[maxN],t[maxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >>n>>m;
    val['A']=0;
    val['G']=1;
    val['C']=2;
    val['U']=3;
    for(int i=1;i<=n;i++)
    {
        cin >> s[i];
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        t[i]=s[i];
        reverse(t[i].begin(),t[i].end());
        add(t[i],i);
    }
    for(int i=1;i<=n;i++)
    {
        TrieInsert(s[i],i);
    }
    string p,q;
    for(int i=1;i<=m;i++)
    {
        cin >> p >> q;
        reverse(q.begin(),q.end());
        TrieNode *x=root1;
        bool ok=true;
        for(int j=0;j<q.size();j++)
        {
            ll nxt=val[q[j]];
            if(x->child[nxt]==nullptr)
            {
                ok=false;
                break;
            }
            else x=x->child[nxt];
        }
        ll l=0,r=0;
        if(ok&&x->pos.size()>0)
        {
            l=x->pos[0];
            r=x->pos.back();
        }
        TrieNode *pp=root;
        for(int j=0;j<p.size();j++)
        {
            ll nxt=val[p[j]];
            if(pp->child[nxt]==nullptr)
            {
                ok=false;
                break;
            }
            else pp=pp->child[nxt];
        }
        if(ok&&pp->pos.size()>0)
        {
            cout << upper_bound(pp->pos.begin(),pp->pos.end(),r)-lower_bound(pp->pos.begin(),pp->pos.end(),l)<<'\n';
        }
        else
        {
            cout <<0<<'\n';
        }
    }
}

Compilation message

selling_rna.cpp: In function 'void TrieInsert(const string&, ll)':
selling_rna.cpp:24:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         int nxt=val[s[i]];
      |                         ^
selling_rna.cpp: In function 'void add(const string&, ll)':
selling_rna.cpp:36:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |         int nxt=val[s[i]];
      |                         ^
selling_rna.cpp: In function 'bool cmp(std::string, std::string)':
selling_rna.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   47 |     for(int i=0;i<min(x.length(),y.length());i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j=0;j<q.size();j++)
      |                     ~^~~~~~~~~
selling_rna.cpp:91:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   91 |             ll nxt=val[q[j]];
      |                            ^
selling_rna.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<p.size();j++)
      |                     ~^~~~~~~~~
selling_rna.cpp:108:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  108 |             ll nxt=val[p[j]];
      |                            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 6 ms 12856 KB Output is correct
3 Correct 7 ms 12848 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 6 ms 12788 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 7 ms 12856 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 225868 KB Output is correct
2 Correct 267 ms 216832 KB Output is correct
3 Correct 331 ms 224748 KB Output is correct
4 Correct 299 ms 214812 KB Output is correct
5 Correct 280 ms 246832 KB Output is correct
6 Correct 267 ms 250316 KB Output is correct
7 Correct 175 ms 53212 KB Output is correct
8 Correct 303 ms 182312 KB Output is correct
9 Correct 278 ms 160692 KB Output is correct
10 Correct 243 ms 154696 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15892 KB Output is correct
2 Correct 35 ms 15736 KB Output is correct
3 Correct 41 ms 15520 KB Output is correct
4 Correct 31 ms 15260 KB Output is correct
5 Correct 34 ms 15532 KB Output is correct
6 Correct 43 ms 15612 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 6 ms 12856 KB Output is correct
3 Correct 7 ms 12848 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 6 ms 12788 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 7 ms 12856 KB Output is correct
8 Correct 266 ms 225868 KB Output is correct
9 Correct 267 ms 216832 KB Output is correct
10 Correct 331 ms 224748 KB Output is correct
11 Correct 299 ms 214812 KB Output is correct
12 Correct 280 ms 246832 KB Output is correct
13 Correct 267 ms 250316 KB Output is correct
14 Correct 175 ms 53212 KB Output is correct
15 Correct 303 ms 182312 KB Output is correct
16 Correct 278 ms 160692 KB Output is correct
17 Correct 243 ms 154696 KB Output is correct
18 Correct 43 ms 15892 KB Output is correct
19 Correct 35 ms 15736 KB Output is correct
20 Correct 41 ms 15520 KB Output is correct
21 Correct 31 ms 15260 KB Output is correct
22 Correct 34 ms 15532 KB Output is correct
23 Correct 43 ms 15612 KB Output is correct
24 Correct 281 ms 193500 KB Output is correct
25 Correct 292 ms 193832 KB Output is correct
26 Correct 265 ms 191748 KB Output is correct
27 Correct 295 ms 191168 KB Output is correct
28 Correct 317 ms 78972 KB Output is correct
29 Correct 131 ms 35312 KB Output is correct