Submission #839435

#	Time	Username	Problem	Language	Result	Execution time	Memory
839435		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1584 ms	242252 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40