Submission #1125119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125119		votranngocvy	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	564 ms	309020 KiB

selling_rna

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

#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 5;
int n,m;
string s[N],p[N],q[N];

struct Trie {
    struct Node {
        Node *child[4];
        int idx;
        vector<int>vec;
        Node(int _num) {
            for (int i = 0; i < 4; i++) child[i] = NULL;
            idx = _num;
            vec.clear();
        }
    };
    int cur,numNode;
    Node *root;
    Trie(): cur(0) {
        numNode = 0;
        root = new Node(numNode);
    };
    void add(string &s,int id) {
        Node *p = root;
        for (auto x: s) {
            int c = 0;
            if (x == 'A') c = 0;
            else if (x == 'G') c = 1;
            else if (x == 'C') c = 2;
            else if (x == 'U') c = 3;
            if (p -> child[c] == NULL) p -> child[c] = new Node(++numNode);
            p = p -> child[c];
            (p -> vec).push_back(id);
        }
    }
    vector<int> get(string &s) {
        Node *p = root;
        for (auto x: s) {
            int c = 0;
            if (x == 'A') c = 0;
            else if (x == 'G') c = 1;
            else if (x == 'C') c = 2;
            else if (x == 'U') c = 3;
            if (p -> child[c] == NULL) {
                vector<int>nullVec;
                return nullVec;
            }
            p = p -> child[c];
        }
        return (p -> vec);
    }
    int getNum(string &s) {
        Node *p = root;
        for (auto x: s) {
            int c = 0;
            if (x == 'A') c = 0;
            else if (x == 'G') c = 1;
            else if (x == 'C') c = 2;
            else if (x == 'U') c = 3;
            if (p -> child[c] == NULL) return 0;
            p = p -> child[c];
        }
        return (p -> vec).size();
    }
    int getIdx(string &s) {
        Node *p = root;
        for (auto x: s) {
            int c = 0;
            if (x == 'A') c = 0;
            else if (x == 'G') c = 1;
            else if (x == 'C') c = 2;
            else if (x == 'U') c = 3;
            if (p -> child[c] == NULL) return 0;
            p = p -> child[c];
        }
        return (p -> idx);
    }
    vector<int>tin,tout;
    int timeDFS;
    void dfs(Node *u) {
        tin[u -> idx] = ++timeDFS;
        for (int i = 0; i < 4; i++)
            if (u -> child[i] != NULL) dfs(u -> child[i]);
        tout[u -> idx] = timeDFS;
    }
    void build() {
        tin.assign(numNode + 2,0);
        tout.assign(numNode + 2,0);
        timeDFS = 0;
        Node *p = root;
        dfs(p);
    }
};

namespace sub2 {
    Trie pre,suf;
    int vis[5005];
    void solve() {
        for (int i = 1; i <= n; i++) {
            pre.add(s[i],i);
            reverse(s[i].begin(),s[i].end());
            suf.add(s[i],i);
            reverse(s[i].begin(),s[i].end());
        }
        for (int i = 1; i <= m; i++) {
            vector<int>tmp1 = pre.get(p[i]);
            vector<int>tmp2 = suf.get(q[i]);
            for (auto x: tmp1) vis[x] = 1;
            int ans = 0;
            for (auto x: tmp2)
                if (vis[x]) ans++;
            cout << ans << "\n";
            for (auto x: tmp1) vis[x] = 0;
        }
    }
}

namespace sub3 {
    Trie suf,T[350];
    map<string,int>mp;
    bool check_condition() {
        int sumS = 0,sumP = 0,sumQ = 0;
        for (int i = 1; i <= n; i++) sumS += s[i].size();
        for (int i = 1; i <= m; i++) {
            sumP += p[i].size();
            sumQ += q[i].size();
        }
        return (sumS <= 1e5 && sumP <= 1e5 && sumQ <= 1e5);
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            reverse(s[i].begin(),s[i].end());
            suf.add(s[i],i);
            reverse(s[i].begin(),s[i].end());
        }
        int num = 0;
        for (int i = 1; i <= m; i++) {
            if (mp.find(q[i]) != mp.end()) continue;
            mp[q[i]] = ++num;
            vector<int>tmp = suf.get(q[i]);
            for (auto x: tmp) T[num].add(s[x],x);
        }
        for (int i = 1; i <= m; i++) {
            int id = mp[q[i]];
            cout << T[id].getNum(p[i]) << "\n";
        }
    }
}

namespace sub4 {
    Trie pre,suf;
    const int maxN = 3e6 + 5;
    int ans[N],bit[maxN];
    struct Data {
        int l,r,type,x,idx;
    };
    vector<Data>vec;
    vector<pii>points;
    void update(int i,int x) {
        for (; i < maxN; i += i & (-i)) bit[i] += x;
    }
    int get(int i) {
        int ans = 0;
        for (; i > 0; i -= i & (-i)) ans += bit[i];
        return ans;
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            pre.add(s[i],i);
            reverse(s[i].begin(),s[i].end());
            suf.add(s[i],i);
            reverse(s[i].begin(),s[i].end());
        }
        for (int i = 1; i <= m; i++) {
            pre.add(p[i],i);
            suf.add(q[i],i);
        }
        pre.build();
        suf.build();
        for (int i = 1; i <= n; i++) {
            int x = pre.getIdx(s[i]);
            reverse(s[i].begin(),s[i].end());
            int y = suf.getIdx(s[i]);
            reverse(s[i].begin(),s[i].end());
            x = pre.tin[x],y = suf.tin[y];
            points.push_back({y,x});
        }
        for (int i = 1; i <= m; i++) {
            int x = pre.getIdx(p[i]);
            int y = suf.getIdx(q[i]);
            vec.push_back({pre.tin[x],pre.tout[x],-1,suf.tin[y] - 1,i});
            vec.push_back({pre.tin[x],pre.tout[x],1,suf.tout[y],i});
        }
        sort(vec.begin(),vec.end(),[&](Data &a,Data &b) {
             return a.x < b.x;
        });
        sort(points.begin(),points.end());
        int j = 0;
        for (int i = 0; i < (int)vec.size(); i++) {
            while (j < (int)points.size() && points[j].fi <= vec[i].x) {
                update(points[j].se,1);
                j++;
            }
            ans[vec[i].idx] += vec[i].type * (get(vec[i].r) - get(vec[i].l - 1));
        }
        for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= m; i++) {
        cin >> p[i] >> q[i];
        reverse(q[i].begin(),q[i].end());
    }
    //if (n <= 5000 && m <= 5000) sub2::solve();
    //else if (sub3::check_condition()) sub3::solve();
    //else
        sub4::solve();
}

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