Submission #638526

#	Time	Username	Problem	Language	Result	Execution time	Memory
638526		NintsiChkhaidze	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1588 ms	7896 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r

#define int ll
using namespace std;
 
const int N = 100005,mod = 1000000007;
int p[N],cnt[N],h[N];
string s[N];

map <int,vector <pair<pair<int,int>,int> > > v;

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,m;
    cin>>n>>m;

    p[0] = 1;
    for (int i = 1; i <= 100000; i++)
        p[i] = (p[i - 1]*31)%mod;

    for (int i = 1; i <= n; i++)
        cin>>s[i];
    
    for (int j = 1; j <= m; j++){
        string a,b;
        cin>>a>>b;

        int A = a.size(),B = b.size(),ha = 0,hb = 0;
        for (int i = 0; i < A; i++) ha = (ha + (p[i]*(a[i] - 'A' + 1)))%mod;
        for (int i = 0; i < B; i++) hb = (hb + (p[i]*(b[i] - 'A' + 1)))%mod;

        v[ha].pb({{hb,B},j});
    }

    for (int i = 1; i <= n; i++){
        int len = s[i].size();
        for (int j = 0; j < len; j++){
            if(j) h[j] = (h[j - 1] + (p[j]*(s[i][j] - 'A' + 1))%mod)%mod;
            else h[j] = (s[i][j] - 'A' + 1);
        }

        for (int j = 0; j < s[i].size(); j++){
            for (int k = 0; k < v[h[j]].size(); k++){
                int hb = v[h[j]][k].f.f,B = v[h[j]][k].f.s,ind = v[h[j]][k].s;
                int Hb = ((h[len - 1] - h[len - B - 1])%mod + mod)%mod;
                if (Hb == (hb*p[len - B])%mod) cnt[ind]++;
            }
        }
    }

    for (int j = 1; j <= m; j++)
        cout<<cnt[j]<<"\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:49:27: 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]
   49 |         for (int j = 0; j < s[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~
selling_rna.cpp:50:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int k = 0; k < v[h[j]].size(); k++){
      |                             ~~^~~~~~~~~~~~~~~~

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