oj.uz

Submission #839435

# Submission time Handle Problem Language Result Execution time Memory
839435 2023-08-30T03:08:07 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 242252 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 2207;
const int base = 31;
const int sqr = 350;

int n, q;

int cnt[maxn];

struct hashsus {
    long long operator() (const pair<int, int> &a)const {
        return 1LL*mod*a.first + a.second;
    }
};

unordered_map<int, vector<int>> mp[2];
unordered_map<pair<int, int>, int, hashsus> mpq;

int main()
{
    cin >> n >> q;
    string str;
    for(int i = 1; i <= n; i++){
        cin >> str;
        if(str.size() >= sqr) {
            int val = 0;
            for(int j = 0; j < str.size(); j++) {
                auto v = str[j];
                val = (1LL*val*base + (v - 'A' + 1))%mod;
                mp[0][val].push_back(i);
            }
            val = 0;
            for(int j = str.size() - 1; j >= 0; j--) {
                auto v = str[j];
                val = (1LL*val*base + (v - 'A' + 1))%mod;
                mp[1][val].push_back(i);
            }
        }
        else {
            int pfx = 0;
            for(int j = 0; j < str.size(); j++){
                pfx = (1LL*pfx*base + (str[j] - 'A' + 1))%mod;
                int sfx = 0;
                for(int k = str.size()-1; k >= 0; k--){
                    sfx = (1LL*sfx*base + (str[k] - 'A' + 1))%mod;
                    mpq[{pfx, sfx}]++;
                }
            }
        }
    }
    string P, Q;
    while(q--){
        int pfx = 0, sfx = 0;
        cin >> P >> Q;
        for(int i = 0; i < P.size(); i++){
            pfx = (1LL*pfx*base + P[i] - 'A' + 1)%mod;
        }
        for(int i = Q.size()-1; i >= 0; i--){
            sfx = (1LL*sfx*base + Q[i] - 'A' + 1)%mod;
        }
        vector<int> v1 = mp[0][pfx], v2 = mp[1][sfx];
        int ans = mpq[{pfx, sfx}];
        for(auto v: v1)cnt[v]++;
        for(auto v: v2)cnt[v]++;
        for(auto v: v1){
            ans += (cnt[v] == 2);
        }
        for(auto v: v1)cnt[v]--;
        for(auto v: v2)cnt[v]--;
        cout << ans << "\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int j = 0; j < str.size(); j++) {
      |                            ~~^~~~~~~~~~~~
selling_rna.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j = 0; j < str.size(); j++){
      |                            ~~^~~~~~~~~~~~
selling_rna.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i = 0; i < P.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1000 KB Output is correct
2 Correct 80 ms 4064 KB Output is correct
3 Correct 72 ms 2356 KB Output is correct
4 Correct 62 ms 924 KB Output is correct
5 Correct 69 ms 3936 KB Output is correct
6 Correct 77 ms 2388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 1584 ms 242252 KB Time limit exceeded
9 Halted 0 ms 0 KB -