Submission #1065728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065728		VMaksimoski008	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1555 ms	313684 KiB

selling_rna

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct Node {
    int in, out;
    map<char, Node*> mp;

    Node() {}
};

struct Trie {
    Node *root;
    int timer = 0;

    Trie() { root = new Node(); }
    ~Trie() { delete root; }

    void insert(string s) {
        Node *u = root;
        for(char &ch : s) {
            if(!u->mp.count(ch)) u->mp[ch] = new Node();
            u = u->mp[ch];
        }
    }

    pii search(string s) {
        Node *u = root;
        for(char &ch : s) {
            if(!u->mp.count(ch)) return { -1, -1 };
            u = u->mp[ch];
        }
        return { u->in, u->out };
    }

    void dfs(Node *u) {
        u->in = timer++;
        for(auto &x : u->mp) dfs(x.second);
        u->out = timer;
    }

    void callDFS() {
        dfs(root);
    }
};

struct BIT {
    int n;
    vector<int> tree;

    BIT(int _n) : n(_n+50), tree(_n+100) {}

    void update(int p, int v) { for(p++; p<n; p+=p&-p) tree[p] += v; }
    int query(int p) { int ans = 0; for(p++; p; p-=p&-p) ans += tree[p]; return ans;}
};

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

    int n, q;
    cin >> n >> q;

    Trie trie, rev_trie;
    vector<string> vec(n);
    for(int i=0; i<n; i++) {
        cin >> vec[i];
        trie.insert(vec[i]);
        reverse(vec[i].begin(), vec[i].end());
        rev_trie.insert(vec[i]);
        reverse(vec[i].begin(), vec[i].end());
    }

    trie.callDFS();
    rev_trie.callDFS();

    vector<array<int, 5> > qus;
    vector<int> ans(q);
    for(int i=0; i<q; i++) {
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());
        auto [in1, out1] = trie.search(a);
        auto [in2, out2] = rev_trie.search(b);
        if(in1 == -1 || in2 == -1) continue;
        qus.push_back({ i, in1, in2, out1, out2 });
    }

    vector<array<int, 4> > ptr(n);
    for(int i=0; i<n; i++) {
        ptr[i][0] = trie.search(vec[i]).first;
        ptr[i][1] = trie.search(vec[i]).second;
        reverse(vec[i].begin(), vec[i].end());
        ptr[i][2] = rev_trie.search(vec[i]).first;
        ptr[i][3] = rev_trie.search(vec[i]).second;
    }

    for(auto &x : qus) {
        // cout << x[1] << " " << x[2] << " " << x[3] << " " << x[4] << '\n';
        for(auto &[a, b, c, d] : ptr)
            if(x[1] <= a && b <= x[3] && x[2] <= c && d <= x[4]) ans[x[0]]++;        
    }

    for(int &x : ans) cout << x << '\n';
    return 0;
}

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