Submission #1065761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065761		VMaksimoski008	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	340 ms	460304 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; }
    int query(int l, int r) { return query(r) - query(l-1); }
};

const int M = 2e6 + 5;
vector<int> by_x[M];
vector<array<int, 3> > on[M], off[M];

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 });
    }
    
    for(int i=0; i<n; i++) {
        int a = trie.search(vec[i]).first;
        reverse(vec[i].begin(), vec[i].end());
        int b = rev_trie.search(vec[i]).first;
        by_x[a].push_back(b);
    }

    for(auto &[id, x1, y1, x2, y2] : qus) {
        on[x2-1].push_back({ id, y1, y2-1 });
        off[x1-1].push_back({ id, y1, y2-1 });
    }

    BIT bit(M);
    for(int i=0; i<M; i++) {
        for(int &p : by_x[i]) bit.update(p, 1);
        for(auto &[id, l, r] : off[i]) ans[id] -= bit.query(l, r);
        for(auto &[id, l, r] : on[i]) ans[id] += bit.query(l, r);
    }

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

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