Submission #362507

#	Time	Username	Problem	Language	Result	Execution time	Memory
362507		denkendoemeer	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	652 ms	345964 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define rit string::reverse_iterator
ll n,m;
struct tri
{
    map<char,tri*>ch;
    vector<ll>ind;
    void insert(rit st,rit dr,ll poz)
    {
        ind.push_back(poz);
        if (st==dr)
            return ;
        char cha=*st;
        if (ch.find(cha)==ch.end())
            ch[cha]=new tri();
        ch[cha]->insert(next(st),dr,poz);
    }
    ll cnt(rit st,rit dr,ll l,ll r)
    {
        if (st==dr)
            return lower_bound(ind.begin(),ind.end(),r)-lower_bound(ind.begin(),ind.end(),l);
        char cha=*st;
        if (ch.find(cha)==ch.end())
            return 0;
        return ch[cha]->cnt(next(st),dr,l,r);
    }
}trie;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld\n",&n,&m);
    vector<string>s(n);
    ll i;
    for(i=0;i<n;i++)
        cin>>s[i];
    sort(s.begin(),s.end());
    for(i=0;i<n;i++)
        trie.insert(s[i].rbegin(),s[i].rend(),i);
    while(m--){
        string x,y;
        cin>>x>>y;
        ll st=lower_bound(s.begin(),s.end(),x)-s.begin();
        ++x.back();
        ll dr=lower_bound(s.begin(),s.end(),x)-s.begin();
        printf("%lld\n",trie.cnt(y.rbegin(),y.rend(),st,dr));
    }
return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%lld%lld\n",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

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