Submission #1280032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280032		minhfxb	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	481 ms	330688 KiB

selling_rna

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

#define endl '\n'
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define REP(i, n) for(int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for(int i = (n); i >= 1; i--)
#define FOR(i, k, n) for(int i = (k), _n = (n); i <= _n; ++i)
#define FOV(i, k, n) for(int i = (k), _n = (n); i >= _n; --i)
#define MASK(i) (1LL << (i))
#define NUM_BIT(i) (__builtin_popcountll(i))
#define BIT(i, mask) ((mask & MASK(i)) != 0)
#define OFF(i, mask) (mask ^ MASK(i))
#define ON(i, mask) (mask | MASK(i))

const int BS = 450;
const int LOG = 18;
const int NMOD = 5;
const int NBASE = 3;
const int base[] = {0, 29, 31};
const int MOD[] = {0, (int)1e9 + 7, (int)998244353, (int)1e9 + 5277};
const int hx[] = {0,  0, 0, 1, -1};
const int hy[] = {0, -1, 1, 0,  0};
const int mod = 1e9 + 22071997;
const int MAXS = 1e4 + 5;
const int MAXN = 1e5 + 5;

int n, m, cur;
vector<string> s;

int w(char s) {
    if (s == 'A') return 0;
    if (s == 'U') return 1;
    if (s == 'G') return 2;
    if (s == 'X') return 3;
}

struct Node {
    Node* child[4];
    int ex;
    int l, r;
    vector<int> id;
    Node() {
        memset(child, NULL, sizeof child);
        ex = 0;
        l = r = 0;
        id.clear();
    }
};

Node* root = new Node();
Node* rootpre = new Node();
Node* rootsuf = new Node();

void add(string s) {
    Node* k = root;
    FOR (i, 0, s.size() - 1) {
        if (k -> child[w(s[i])] == NULL) k -> child[w(s[i])] = new Node();
        k = k -> child[w(s[i])];
    }
    k -> ex++;
}

void dfs(Node* k, string t) {
    if (k -> child[0] != NULL) dfs(k -> child[0], t + 'A');
    if (k -> child[1] != NULL) dfs(k -> child[1], t + 'U');
    if (k -> child[2] != NULL) dfs(k -> child[2], t + 'G');
    if (k -> child[3] != NULL) dfs(k -> child[3], t + 'X');
    while (k -> ex--) s.pb(t);
}

void addpre(string s, int id) {
    Node* k = rootpre;
    FOR (i, 0, s.size() - 1) {
        if (k -> child[w(s[i])] == NULL) {
                k -> child[w(s[i])] = new Node();
                k -> child[w(s[i])] -> l = id;
                k -> child[w(s[i])] -> r = id;
        }
        else k -> child[w(s[i])] -> r++;
        k = k -> child[w(s[i])];
    }
}

void addsuf(string s, int id) {
    reverse(s.begin(), s.end());
    Node* k = rootsuf;
    FOR (i, 0, s.size() - 1) {
        if (k -> child[w(s[i])] == NULL) k -> child[w(s[i])] = new Node();
        k = k -> child[w(s[i])];
        k -> id.pb(id);
    }
}

pii getpre(string s) {
    Node* k = rootpre;
    FOR (i, 0, s.size() - 1) {
        if (k -> child[w(s[i])] == NULL) return {0, 0};
        k = k -> child[w(s[i])];
    }
    return {k -> l, k -> r};
}

int getsuf(string t, string s) {
    pii p = getpre(t);
    int l = p.fi;
    int r = p.se;
    if (!l) return 0;
    Node* k = rootsuf;
    reverse(s.begin(), s.end());
    FOR (i, 0, s.size() - 1) {
        if (k -> child[w(s[i])] == NULL) return 0;
        k = k -> child[w(s[i])];
    }
    vector<int> ve = k -> id;
    return (upper_bound(ve.begin(), ve.end(), r) - lower_bound(ve.begin(), ve.end(), l));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("threejug.inp", "r", stdin);
//    freopen("threejug.out", "w", stdout);
    cin >> n >> m;
    REP (i, n) {
        string x;
        cin >> x;
        add(x);
    }
    s.pb("nger");
    dfs(root, "");
    REP (i, n) {
        addpre(s[i], i);
        addsuf(s[i], i);
    }
    REP (i, m) {
        string x, y;
        cin >> x >> y;
        cout << getsuf(x, y) << endl;
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In constructor 'Node::Node()':
selling_rna.cpp:51:23: warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]
   51 |         memset(child, NULL, sizeof child);
      |                       ^~~~
In file included from /usr/include/features.h:502,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/c++config.h:679,
                 from /usr/include/c++/13/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:33,
                 from selling_rna.cpp:1:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:57:1: note:   declared here
   57 | __NTH (memset (void *__dest, int __ch, size_t __len))
      | ^~~~~
selling_rna.cpp: In function 'int w(char)':
selling_rna.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

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