oj.uz

Submission #638543

# Submission time Handle Problem Language Result Execution time Memory
638543 2022-09-06T10:58:06 Z NintsiChkhaidze Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 301196 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Correct 7 ms 8928 KB Output is correct
3 Correct 7 ms 8928 KB Output is correct
4 Correct 7 ms 8916 KB Output is correct
5 Correct 5 ms 8916 KB Output is correct
6 Correct 7 ms 8924 KB Output is correct
7 Correct 5 ms 8928 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 27964 KB Output is correct
2 Correct 673 ms 28152 KB Output is correct
3 Runtime error 831 ms 301196 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 13640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Correct 7 ms 8928 KB Output is correct
3 Correct 7 ms 8928 KB Output is correct
4 Correct 7 ms 8916 KB Output is correct
5 Correct 5 ms 8916 KB Output is correct
6 Correct 7 ms 8924 KB Output is correct
7 Correct 5 ms 8928 KB Output is correct
8 Correct 599 ms 27964 KB Output is correct
9 Correct 673 ms 28152 KB Output is correct
10 Runtime error 831 ms 301196 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -