Submission #1278369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278369		assazzin_2	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	502 ms	558240 KiB

selling_rna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define ll long long
const int mod = 676767677;
const ll inf = 1e18 + 500;
const long double EPS = 1e-10;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}

const int LOG = 21;
const int N = 2000010;
const int MAX = 2000010 * LOG;
int seg[4 * N];

struct Trie {
    int cnt;
    int nx[MAX][4];
    int sz[MAX];

    void init(){
        cnt = 0;
    }

    int addnode() {
        sz[cnt] = 0;
        memset(nx[cnt], -1, sizeof(nx[cnt]));
        return cnt++;
    }

    void add(int root, string &s) {
        for (int i = s.size() - 1; i >= 0; i--) {
            char c = s[i];
            if (nx[root][c - 'A'] == -1)
                nx[root][c - 'A'] = addnode();
            root = nx[root][c - 'A'];
            sz[root]++;
        }
    }
}t;

int n, m;
string a[N];

void build(int id, int tl, int tr) {
    seg[id] = t.addnode();
    for (int i = tl; i <= tr; i++)
        t.add(seg[id], a[i]);
    if (tl == tr) return;
    int md = (tl + tr)/2;
    build(2*id, tl, md);
    build(2*id+1, md+1, tr);
}

int lower_bound(string &s) {
    int l = 0, r = n - 1, ret = n;
    while (l <= r) {
        int md = (l + r) / 2;
        if (s <= a[md].substr(0, s.size())) {
            ret = md;
            r = md - 1;
        }else l = md + 1;
    }
    return ret;
}

int upper_bound(string &s) {
    int l = 0, r = n - 1, ret = n;
    while (l <= r) {
        int md = (l + r) / 2;
        if (s < a[md].substr(0, s.size())) {
            ret = md;
            r = md - 1;
        }else l = md + 1;
    }
    return ret;
}

int get(int root, string &q) {
    for (char c : q) {
        if (t.nx[root][c - 'A'] == -1) return 0;
        root = t.nx[root][c - 'A'];
    }
    return t.sz[root];
}

int get(int id, int tl, int tr, int l, int r, string &q) {
    if (tl > r || tr < l) return 0;
    if (tl >= l && tr <= r) return get(seg[id], q);
    int md = (tl + tr)/2;
    return get(2*id, tl, md, l, r, q) + get(2*id+1, md+1, tr, l, r, q);
}

string conv(string s) {
    for (char &c : s) {
        if (c == 'C') c = 'B';
        else if (c == 'G') c = 'C';
        else if (c == 'U') c = 'D'; 
    }
    return s;
}

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

    for (int i = 0; i < n; i++){
        cin >> a[i];
        a[i] = conv(a[i]);
    }
    sort(a, a + n);

    build(1, 0, n - 1);

    while (m--) {
        string p, q;
        cin >> p >> q;
        
        p = conv(p);
        q = conv(q);
        reverse(q.begin(), q.end());

        int l = lower_bound(p);
        int r = upper_bound(p) - 1;
        
        if (l > r) {
            cout << 0 << endl; 
            continue;
        }
        cout << get(1, 0, n - 1, l, r, q) << endl;
    }
}   

int main(){
    FAST

    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    // #endif

    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

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