oj.uz

Submission #849665

# Submission time Handle Problem Language Result Execution time Memory
849665 2023-09-15T07:46:14 Z alexdd Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 306 ms 452176 KB 
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const int cst = 31;
int n,m;
vector<int> trie[2000005];
int mch[2000005][26];
vector<int> trie2[2000005];
int mch2[2000005][26];
int rez[100005];
int cnt,cnt2;
int poze[2000005],timer=0;
int siz[2000005];
int op[100005];
int mp[2000005];
vector<pair<pair<int,int>,int>> qrys[100005];
vector<int> pozs[100005];
void dfs(int nod)
{
    poze[nod]=++timer;
    siz[nod]=1;
    for(auto adj:trie[nod])
    {
        dfs(adj);
        siz[nod]+=siz[adj];
    }
}
int v[2000005];
void solve(int suff)
{
    int cntv=0;
    sort(pozs[suff].begin(),pozs[suff].end());
    for(auto x:qrys[suff])
        rez[x.second] = upper_bound(pozs[suff].begin(),pozs[suff].end(),x.first.second) - lower_bound(pozs[suff].begin(),pozs[suff].end(),x.first.first);
}
int ult[100005];
string cit[100005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    string s,p,q;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        cit[i]=s;
        int nod=0;
        for(int j=0;j<s.size();j++)
        {
            if(mch[nod][s[j]-'A']==0)
            {
                cnt++;
                mch[nod][s[j]-'A']=cnt;
                trie[nod].push_back(cnt);
            }
            nod=mch[nod][s[j]-'A'];
        }
        ult[i]=nod;
    }
    dfs(0);
    for(int i=1;i<=m;i++)
    {
        cin>>p>>q;
        int nod=0;
        bool bl=0;
        for(int j=0;j<p.size();j++)
        {
            if(mch[nod][p[j]-'A']==0)
            {
                bl=1;
                break;
            }
            nod=mch[nod][p[j]-'A'];
        }
        if(!bl)
        {
            int nod2=0;
            for(int j=q.size()-1;j>=0;j--)
            {
                if(mch2[nod2][q[j]-'A']==0)
                {
                    cnt2++;
                    mch2[nod2][q[j]-'A']=cnt2;
                    trie2[nod2].push_back(cnt2);
                }
                nod2=mch2[nod2][q[j]-'A'];
            }
            ///qrys[nod].push_back({curaux,i});
            if(mp[nod2]==0) mp[nod2]=i;
            op[i]=nod2;
            qrys[mp[nod2]].push_back({{poze[nod],poze[nod]+siz[nod]-1},i});
        }
    }
    for(int i=1;i<=n;i++)
    {
        s=cit[i];
        int nod2=0;
        for(int j=s.size()-1;j>=0;j--)
        {
            if(mch2[nod2][s[j]-'A']==0)
            {
                cnt2++;
                mch2[nod2][s[j]-'A']=cnt2;
                trie2[nod2].push_back(cnt2);
            }
            nod2=mch2[nod2][s[j]-'A'];
            if(mp[nod2]!=0) pozs[mp[nod2]].push_back(poze[ult[i]]);
        }
    }
    for(int i=m;i>0;i--)
    {
        if(mp[op[i]]==i)
        {
            solve(i);
        }
    }
    for(int i=1;i<=m;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

Compilation message

selling_rna.cpp: In function 'void solve(int)':
selling_rna.cpp:31:9: warning: unused variable 'cntv' [-Wunused-variable]
   31 |     int cntv=0;
      |         ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~
selling_rna.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<p.size();j++)
      |                     ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 110680 KB Output is correct
2 Correct 25 ms 111196 KB Output is correct
3 Correct 23 ms 110796 KB Output is correct
4 Correct 24 ms 110684 KB Output is correct
5 Correct 23 ms 110836 KB Output is correct
6 Correct 23 ms 110684 KB Output is correct
7 Correct 23 ms 110684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 374360 KB Output is correct
2 Correct 214 ms 360164 KB Output is correct
3 Correct 296 ms 394012 KB Output is correct
4 Correct 306 ms 382144 KB Output is correct
5 Correct 269 ms 447264 KB Output is correct
6 Correct 270 ms 452176 KB Output is correct
7 Correct 74 ms 119892 KB Output is correct
8 Correct 221 ms 310352 KB Output is correct
9 Correct 199 ms 277480 KB Output is correct
10 Correct 187 ms 274304 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 112268 KB Output is correct
2 Correct 34 ms 112444 KB Output is correct
3 Correct 36 ms 112208 KB Output is correct
4 Correct 31 ms 111772 KB Output is correct
5 Correct 36 ms 112220 KB Output is correct
6 Correct 39 ms 112188 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 110680 KB Output is correct
2 Correct 25 ms 111196 KB Output is correct
3 Correct 23 ms 110796 KB Output is correct
4 Correct 24 ms 110684 KB Output is correct
5 Correct 23 ms 110836 KB Output is correct
6 Correct 23 ms 110684 KB Output is correct
7 Correct 23 ms 110684 KB Output is correct
8 Correct 209 ms 374360 KB Output is correct
9 Correct 214 ms 360164 KB Output is correct
10 Correct 296 ms 394012 KB Output is correct
11 Correct 306 ms 382144 KB Output is correct
12 Correct 269 ms 447264 KB Output is correct
13 Correct 270 ms 452176 KB Output is correct
14 Correct 74 ms 119892 KB Output is correct
15 Correct 221 ms 310352 KB Output is correct
16 Correct 199 ms 277480 KB Output is correct
17 Correct 187 ms 274304 KB Output is correct
18 Correct 36 ms 112268 KB Output is correct
19 Correct 34 ms 112444 KB Output is correct
20 Correct 36 ms 112208 KB Output is correct
21 Correct 31 ms 111772 KB Output is correct
22 Correct 36 ms 112220 KB Output is correct
23 Correct 39 ms 112188 KB Output is correct
24 Correct 190 ms 326228 KB Output is correct
25 Correct 201 ms 326892 KB Output is correct
26 Correct 190 ms 323476 KB Output is correct
27 Correct 283 ms 344072 KB Output is correct
28 Correct 116 ms 144212 KB Output is correct
29 Correct 59 ms 113492 KB Output is correct