Submission #1260278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260278		pvb.tunglam	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	172 ms	142024 KiB

selling_rna

#include <bits/stdc++.h>
#define hash _hash_
#define y1 _y1_
#define dec _dec_
using namespace std;

using ll = long long;
using ull = unsigned long long;
const ll MOD = 1e9 + 7;
const ll oo  = 1e18;

/*----------- I alone decide my fate! ------------*/
/*  I just do what I gotta, in the heat of the summer...  */

// mapping: A -> 0, G -> 1, C -> 2, U -> 3
int get_val(char c) {
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}

// so sánh theo thứ tự A < G < C < U
bool cmp_str(const string &a, const string &b) {
    int n = (int)a.size(), m = (int)b.size();
    int k = min(n, m);
    for (int i = 0; i < k; ++i) {
        int xa = get_val(a[i]);
        int xb = get_val(b[i]);
        if (xa != xb) return xa < xb;
    }
    return n < m;
}

// trie tiền tố (để lấy khoảng [L, R] các xâu có tiền tố p)
#define MAXNODE 2000005
int ch1[MAXNODE][4];
int L1[MAXNODE], R1[MAXNODE];
int cur1;

void pref_init() {
    cur1 = 0;
    for (int j = 0; j < 4; ++j) ch1[0][j] = -1;
    L1[0] = 1000000000; R1[0] = -1000000000;
}
int pref_new() {
    ++cur1;
    for (int j = 0; j < 4; ++j) ch1[cur1][j] = -1;
    L1[cur1] = 1000000000; R1[cur1] = -1000000000;
    return cur1;
}
void pref_add(const string &s, int id) {
    int u = 0;
    for (char c : s) {
        int t = get_val(c);
        if (ch1[u][t] == -1) ch1[u][t] = pref_new();
        u = ch1[u][t];
        if (L1[u] > id) L1[u] = id;
        if (R1[u] < id) R1[u] = id;
    }
}
void pref_get_range(const string &s, int &L, int &R) {
    int u = 0;
    for (char c : s) {
        int t = get_val(c);
        if (ch1[u][t] == -1) { L = -1; R = -1; return; }
        u = ch1[u][t];
    }
    L = L1[u]; R = R1[u];
}

// trie hậu tố trên xâu đảo (để đếm số id thuộc [L, R] có hậu tố q)
int ch2[MAXNODE][4];
vector<int> ids2[MAXNODE];
int cur2;

void suf_init() {
    cur2 = 0;
    for (int j = 0; j < 4; ++j) ch2[0][j] = -1;
    ids2[0].clear();
}
int suf_new() {
    ++cur2;
    for (int j = 0; j < 4; ++j) ch2[cur2][j] = -1;
    ids2[cur2].clear();
    return cur2;
}
void suf_add(string s, int id) {
    reverse(s.begin(), s.end());
    int u = 0;
    for (char c : s) {
        int t = get_val(c);
        if (ch2[u][t] == -1) ch2[u][t] = suf_new();
        u = ch2[u][t];
        ids2[u].push_back(id); // id tăng dần
    }
}
int suf_query(string s, int L, int R) {
    reverse(s.begin(), s.end());
    int u = 0;
    for (char c : s) {
        int t = get_val(c);
        if (ch2[u][t] == -1) return 0;
        u = ch2[u][t];
    }
    const vector<int> &v = ids2[u];
    int l = (int)(lower_bound(v.begin(), v.end(), L) - v.begin());
    int r = (int)(upper_bound(v.begin(), v.end(), R) - v.begin()) - 1;
    if (l > r) return 0;
    return r - l + 1;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end(), cmp_str);

    pref_init();
    suf_init();

    for (int i = 0; i < n; ++i) {
        pref_add(a[i], i + 1);
        suf_add(a[i],  i + 1);
    }

    while (m--) {
        string p, q;
        cin >> p >> q;
        int L, R;
        pref_get_range(p, L, R);
        if (L == -1) {
            cout << 0 << '\n';
        } else {
            cout << suf_query(q, L, R) << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

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