Submission #319664

#	Time	Username	Problem	Language	Result	Execution time	Memory
319664		qpwoeirut	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1561 ms	140180 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)((x).size())

typedef long long ll;

const int MN = 100001;
const int CT = 2;
const ll MOD[CT] = {(ll)1e9 + 7, (ll)1e9+9};
const ll BASE = 5;

int to_int(char c) {
    if (c == 'A') return 1;
    else if (c == 'C') return 2;
    else if (c == 'G') return 3;
    else if (c == 'U') return 4;
    else assert(false);
}

struct Hash {
    int h[CT];

    Hash() {
        fill(h, h+CT, 0);
    }
    Hash(string s) {
        fill(h, h+CT, 0);
        for (int i=sz(s) - 1; i>=0; --i) {
            for (int j=0; j<CT; ++j) {
                h[j] = ((h[j] * BASE) + to_int(s[i])) % MOD[j];
            }
        }
    }
    void add(char c) {
        int val = to_int(c);

        for (int i=0; i<CT; ++i) {
            h[i] = ((h[i] * BASE) + val) % MOD[i];
        }
    }
    inline const bool operator<(const Hash& other) const {
        for (int i=0; i<CT; ++i) {
            if (h[i] != other.h[i]) {
                return h[i] < other.h[i];
            }
        }
        return false;
    }
};

int N, M;
string S[MN];
vector<Hash> phash[MN];
map<Hash, vector<int>> shash;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> M;
    for (int i=0; i<N; ++i) {
        cin >> S[i];
    }
    sort(S, S+N);

    for (int i=0; i<N; ++i) {
        Hash cur;
        for (int j=sz(S[i]) - 1; j>=0; --j) {
            cur.add(S[i][j]);
            shash[cur].emplace_back(i);
        }
    }

    for (int i=0; i<M; ++i) {
        string P, Q;
        cin >> P >> Q;

        int lo = lower_bound(S, S+N, P) - S;
        P.back()++;
        int hi = lower_bound(S, S+N, P) - S;

        Hash suff(Q);
        auto it = shash.find(suff);
        if (it == shash.end()) {
            cout << "0\n";
        } else {
            int mn = lower_bound(it->second.begin(), it->second.end(), lo) - it->second.begin();
            int mx = lower_bound(it->second.begin(), it->second.end(), hi) - it->second.begin();

            cout << mx - mn << '\n';
        }
    }
}
/*
2 3
AUGC
AGC
G C
AU C
A C

3 3
AA
AA AGA
AA AA
AG GA
AG GA

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

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