Submission #896985

#	Time	Username	Problem	Language	Result	Execution time	Memory
896985		Aiperiii	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	401 ms	332116 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2e6;
struct Trie{
    vector <int> v;
    map <char,int> mp;
};
Trie t[N];
int cnt=0;
void insert(string s,int ind){
    int p=0;
    for(int i=0;i<s.size();i++){
        if(t[p].mp[s[i]]==0){
            cnt++;
            t[p].mp[s[i]]=cnt;
        }
        p=t[p].mp[s[i]];
        t[p].v.pb(ind);
    }
}
int get(string s,int l,int r){
    int p=0;
    for(int i=0;i<s.size();i++){
        p=t[p].mp[s[i]];
        if(p==0)return 0;
    }
    auto L=lower_bound(all(t[p].v),l)-t[p].v.begin();
    auto R=upper_bound(all(t[p].v),r)-t[p].v.begin();
    return R-L;
}
signed main(){
    int n,m;
    cin>>n>>m;
    vector <string> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(all(a));
    for(int i=0;i<n;i++){
        string x=a[i];reverse(all(x));
        insert(x,i);
    }
    for(int i=0;i<m;i++){
        string s,q;
        cin>>s>>q;
        auto it=lower_bound(all(a),s);
        int l=it-a.begin();
        s.back()++;
        it=lower_bound(all(a),s);
        int r=it-a.begin()-1;
        if(l>r){
            cout<<0<<"\n";
            continue;
        }
        reverse(all(q));
        cout<<get(q,l,r)<<"\n";
        
    }
}
/*
 
 1
 0 1
 2
 0 1
 3
 0
 4
 1
 5
 1
 */

Compilation message (stderr)

selling_rna.cpp: In function 'void insert(std::string, long long int)':
selling_rna.cpp:17:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'long long int get(std::string, long long int, long long int)':
selling_rna.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

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