Submission #1149159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149159		DP_196	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	150 ms	190412 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & 1)
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }

const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m;
int code[256];
string S[MAXN];

class Trie {
private:
    struct data {
        data *nxt[4];
        int minID, maxID;

        data () {
            for (int i = 0; i < 4; i++) nxt[i] = NULL;
            minID = INF;
            maxID = 0;
        }
    };

public: 
    data *p = new data();
    
    void add(const string &A, const int &ID) {
        data *u = p;
        for (int i = 0; i < sz(A); i++) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) u->nxt[k] = new data();
            u = u->nxt[k];

            minimize(u->minID, ID);
            maximize(u->maxID, ID);
        }
    }

    pair<int, int> get(const string &A) {
        data *u = p;
        for (int i = 0; i < sz(A); i++) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) return {-1, -1};
            u = u->nxt[k];
        }   
        return {u->minID, u->maxID};
    }
};

class ReverseTrie {
private:
    struct data {
        data *nxt[4];
        vector<int> setIDS;

        data () {
            for (int i = 0; i < 4; i++) nxt[i] = 0;
        }
    };

public:
    data *p = new data();

    void add(const string &A, const int &ID) {
        data *u = p;
        for (int i = sz(A) - 1; i >= 0; i--) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) u->nxt[k] = new data();
            u = u->nxt[k];

            u->setIDS.push_back(ID);
        }
    }

    int get(const string &A, int L, int R) {
        data *u = p;
        for (int i = sz(A) - 1; i >= 0; i--) {
            int k = code[A[i]];
            if (u->nxt[k] == NULL) return 0;
            u = u->nxt[k];
        }

        return upper_bound(all(u->setIDS), R) - lower_bound(all(u->setIDS), L);
    }
};

void solve() {
	cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> S[i];

    code['A'] = 0;
    code['U'] = 1;
    code['G'] = 2;
    code['C'] = 3;
    sort(S + 1, S + n + 1);

    Trie tree1;
    ReverseTrie tree2;

    for (int i = 1; i <= n; i++) {
        tree1.add(S[i], i);
        tree2.add(S[i], i);
    }

    for (int i = 1; i <= m; i++) {
        string P, Q;

        cin >> P >> Q;

        pair<int, int> seg = tree1.get(P);
        cout << tree2.get(Q, seg.first, seg.second) << '\n';
    }
}

#define TASK "A"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    //  freopen(TASK".inp", "r", stdin);
    //	freopen(TASK".out", "w", stdout);
    #endif

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
// DP_612

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