oj.uz

Submission #638526

# Submission time Handle Problem Language Result Execution time Memory
638526 2022-09-06T10:46:54 Z NintsiChkhaidze Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 7896 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];
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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4228 KB Output is correct
4 Correct 3 ms 4228 KB Output is correct
5 Correct 3 ms 4232 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 7716 KB Output is correct
2 Execution timed out 1531 ms 7896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4228 KB Output is correct
4 Correct 3 ms 4228 KB Output is correct
5 Correct 3 ms 4232 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 574 ms 7716 KB Output is correct
9 Execution timed out 1531 ms 7896 KB Time limit exceeded
10 Halted 0 ms 0 KB -