제출 #434338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434338		Mike4235	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	344 ms	203504 KiB

selling_rna

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

struct Node1{
    int child[4];
    int l, r;
};

struct Node2{
    int child[4];
    vector<int> id;
};

vector<Node1> Trie1;
vector<Node2> Trie2;

void init1(int i) {
    Node1 tmp;
    memset(tmp.child, -1, sizeof(tmp.child));
    tmp.l = i;
    Trie1.push_back(tmp);
}

void init2() {
    Node2 tmp;
    memset(tmp.child, -1, sizeof(tmp.child));
    Trie2.push_back(tmp);
}

void add(string& s, int id) {
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie1[pos].child[t] == -1) {
            Trie1[pos].child[t] = sz(Trie1);
            init1(id);
        }

        pos = Trie1[pos].child[t];
        Trie1[pos].r = id;
    }

    reverse(s.begin(), s.end());
    pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie2[pos].child[t] == -1) {
            Trie2[pos].child[t] = sz(Trie2);
            init2();
        }

        pos = Trie2[pos].child[t];
        Trie2[pos].id.push_back(id);
    }
}

pii range(string& s) {
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie1[pos].child[t] == -1) return {0, 0};
        pos = Trie1[pos].child[t];
    }

    return {Trie1[pos].l, Trie1[pos].r};
}

int n, q;
string s[100005];

int get(string& s, pii p) {
    reverse(s.begin(), s.end());
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie2[pos].child[t] == -1) return 0;
        pos = Trie2[pos].child[t];
    }

    return upper_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.second) - lower_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.first);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    init1(0); init2();

    cin >> n >> q;
    for1(i,1,n) cin >> s[i];
    sort(s + 1, s + n + 1);
    for1(i,1,n) add(s[i], i);

    while(q--) {
        string pre, suf;
        cin >> pre >> suf;

        auto p = range(pre);
        cout << get(suf, p) << "\n";
    }
    
}

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