Submission #638543

#	Time	Username	Problem	Language	Result	Execution time	Memory
638543		NintsiChkhaidze	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1585 ms	301196 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],ha[N],hb[N],A[N],B[N];
string s[N];
vector <pair<int,int> > v[200005];
map <int,int> mp;
vector <int> val;

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];
        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);
            val.pb(h[j]);
        }
    }
        
    for (int j = 1; j <= m; j++){
        string a,b;
        cin>>a>>b;

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

    sort(val.begin(),val.end());
    int c = 0;
    for (int i = 0; i < val.size(); i++){
        if (!i || val[i] != val[i - 1]) c++;
        mp[val[i]] = c;
    }

    for (int i = 1; i <= m; i++)
        v[mp[ha[i]]].pb({hb[i],i});
    
    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 < len; j++){
            int w = mp[h[j]];
            for (int k = 0; k < v[w].size(); k++){
                int hb = v[w][k].f,ind = v[w][k].s;
                int Hb = ((h[len - 1] - h[len - B[ind] - 1])%mod + mod)%mod;
                if (Hb == (hb*p[len - B[ind]])%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:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < val.size(); i++){
      |                     ~~^~~~~~~~~~~~
selling_rna.cpp:69:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int k = 0; k < v[w].size(); k++){
      |                             ~~^~~~~~~~~~~~~

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