제출 #849635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849635		alexdd	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1549 ms	139396 KiB

selling_rna

#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];
int rez[100005];
int cnt;
int poze[2000005],timer=0;
int siz[2000005];
map<int,int> mp;
int op[100005];
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);
    }
}
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>>cit[i];
        s=cit[i];
        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'];
        }
    }
    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 curaux=0,curp=1;
            for(int j=q.size()-1;j>=0;j--)
            {
                curaux = (curaux + (1LL*curp*(q[j]-'A'+1)%MOD))%MOD;
                curp=(curp*cst)%MOD;
            }
            ///qrys[nod].push_back({curaux,i});
            if(mp[curaux]==0) mp[curaux]=i;
            op[i]=curaux;
            qrys[mp[curaux]].push_back({{poze[nod],poze[nod]+siz[nod]-1},i});
        }
    }
    for(int i=1;i<=n;i++)
    {
        s=cit[i];
        int nod=0;
        for(int j=0;j<s.size();j++)
        {
            nod=mch[nod][s[j]-'A'];
        }
        int curaux=0,curp=1;
        for(int j=s.size()-1;j>=0;j--)
        {
            curaux = (curaux + (1LL*curp*(s[j]-'A'+1)%MOD))%MOD;
            curp=(curp*cst)%MOD;
            ///suffs[nod].push_back(curaux);
            if(mp[curaux]!=0) pozs[mp[curaux]].push_back(poze[nod]);
        }
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40