Submission #947477

#	Time	Username	Problem	Language	Result	Execution time	Memory
947477		Pring	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	102 ms	53220 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 4> A;

const int MXN = 100005, MXM = 2000005;
int n, m;
string s[MXN], p[MXN], q[MXN];
int ans[MXN];
vector<pii> v;
int M[200];

namespace TRIE {
    int nc, cnt[MXM];
    A chd[MXM];

    int new_node() {
        cnt[nc] = 0;
        FOR(i, 0, 4) chd[nc][i] = 0;
        return nc++;
    }

    void init() {
        nc = 2;
    }

    void PUSH(string &s) {
        int now = 1;
        for (auto &i : s) {
            int id = M[i];
            if (chd[now][id] == 0) chd[now][id] = new_node();
            now = chd[now][id];
            cnt[now]++;
        }
    }

    int QUERY(string &s) {
        int now = 1;
        for (auto &i : s) {
            int id = M[i];
            now = chd[now][id];
        }
        debug(s, now, cnt[now]);
        return cnt[now];
    }
}

void miku() {
    M['A'] = 0;
    M['U'] = 1;
    M['C'] = 2;
    M['G'] = 3;
    cin >> n >> m;
    FOR(i, 0, n) cin >> s[i];
    sort(s, s + n);
    FOR(i, 1, m + 1) {
        cin >> p[i] >> q[i];
        reverse(q[i].begin(), q[i].end());
        v.push_back(mp((int) (lower_bound(s, s + n, p[i]) - s), -i));
        p[i].back()++;
        v.push_back(mp((int) (lower_bound(s, s + n, p[i]) - s), i));
    }
    FOR(i, 0, n) v.push_back(mp(i, 0LL));
    sort(v.begin(), v.end(), [](pii a, pii b) -> bool {
        if (a.fs != b.fs) return a.fs < b.fs;
        if (a.sc == 0) return false;
        if (b.sc == 0) return true;
        return a.fs < b.fs;
    });
    // FOR(i, 0, n) cout << s[i] << '\n';
    TRIE::init();
    for (auto [x, type] : v) {
        // debug(x, type);
        if (type == 0) {
            reverse(s[x].begin(), s[x].end());
            debug("PUSH", s[x]);
            TRIE::PUSH(s[x]);
            continue;
        }
        if (type > 0) ans[type] += TRIE::QUERY(q[type]);
        else ans[-type] -= TRIE::QUERY(q[-type]);
    }
    FOR(i, 1, m + 1) cout << ans[i] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void TRIE::PUSH(std::string&)':
selling_rna.cpp:46:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |             int id = M[i];
      |                        ^
selling_rna.cpp: In function 'int TRIE::QUERY(std::string&)':
selling_rna.cpp:56:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |             int id = M[i];
      |                        ^
selling_rna.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
selling_rna.cpp:59:9: note: in expansion of macro 'debug'
   59 |         debug(s, now, cnt[now]);
      |         ^~~~~
selling_rna.cpp: In function 'void miku()':
selling_rna.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
selling_rna.cpp:92:13: note: in expansion of macro 'debug'
   92 |             debug("PUSH", s[x]);
      |             ^~~~~

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