Submission #1034415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034415		doducanh	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	466 ms	697096 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(),x.end()
const int maxn=2e5+7;
const int maxx=2e6+7;
string s[maxn];
int n,m;
struct trie
{
    int t[maxx][30];
    vector<int>who[maxx];
    int cnt;
    trie(){
        cnt=0;
    }
    void add(string &s,int i){
        int curr=0;
        for(char c:s){
            if(t[curr][c-'a'+1]==0)t[curr][c-'a'+1]=++cnt;
            curr=t[curr][c-'a'+1];
            who[curr].push_back(i);
        }
    }
    array<int,2>get(string &s){
        int curr=0;
        for(char c:s){
            if(t[curr][c-'a'+1]==0)return {-1,-1};
            curr=t[curr][c-'a'+1];
        }
        return array<int,2>{who[curr].front(),who[curr].back()};
    }
    int query(string &s,int l,int r){
        int curr=0;
        for(char c:s){
            if(t[curr][c-'a'+1]==0)return 0;
            curr=t[curr][c-'a'+1];
        }
        return (int)(upper_bound(all(who[curr]),r)-lower_bound(all(who[curr]),l));
    }
};
trie t,tn;
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    vector<string>s(n);
    for(string &s:s){
        cin>>s;
    }
    sort(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        t.add(s[i],i);
        reverse(all(s[i]));
        tn.add(s[i],i);
    }
    for(int i=1;i<=m;i++){
        string p,q;
        cin>>p>>q;
        reverse(all(q));
        auto [L,R]=t.get(p);
        cout<<tn.query(q,L,R)<<"\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         auto [L,R]=t.get(p);
      |              ^

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