Submission #940055

#	Time	Username	Problem	Language	Result	Execution time	Memory
940055		phoenix	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1151 ms	769044 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

string str = "ACGU";
map<char, int> mp = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};

struct Node {
    int to[4] = {};
    int link = 0;
    int term = 0;
};

const int N = 100100;
const int M = 4000100;

Node nodes[M];
int numberOfNodes;

Node& node(int i) {
    assert(0 <= i && i <= numberOfNodes);
    return nodes[i]; 
}

int createNode() {
    nodes[++numberOfNodes] = Node();
    return numberOfNodes;
}

int getNext(int v, char c) {
    return node(v).to[mp[c]];
} 
 
int root = createNode();

int getLink(int v, char c) {
    if (!v) return root;
    if (getNext(v, c)) return getNext(v, c);
    return getLink(node(v).link, c);
}

void addWord(string s, int x) {
    int v = root;
    for (char c : s) {
        if (!getNext(v, c))
            node(v).to[mp[c]] = createNode();
        v = getNext(v, c);
    }
    node(v).term += x;
}

bool checkWord(string s) {
    int v = root;
    for (char c : s) {
        if (!getNext(v, c)) return false;
        v = getNext(v, c);
    }
    return true;
}

void build() {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        for (int x = 0; x < 4; x++) {
            int nxt = node(s).to[x];
            if (!nxt) continue;
            node(nxt).link = getLink(node(s).link, str[x]); 
            q.push(nxt);
        }
    }
}

struct Graph {
    vector<int> e[M];
    int ord[M];
    int tin[M], tout[M], T;
    void dfs(int s, int p) {
        tin[s] = ++T;
        ord[T] = s;
        for (int to : e[s]) {
            if (to == p) continue;
            dfs(to, s);
        }
        tout[s] = T;
    }
};

struct Fenwick {
    int tr[M];
    void update(int pos, int val) {
        for (; pos < M; pos += (pos & -pos))
            tr[pos] += val;
    }
    int get(int l, int r) {
        int res = 0;
        for (; r; r -= (r & -r))
            res += tr[r];
        for (--l; l; l -= (l & -l))
            res -= tr[l];
        return res;
    }
};

struct Query {
    int l;
    int r;
    int mul;
    int inx;
};

int n, m;
Graph g1, g2;
Fenwick fnw;
int res[N];

vector<Query> qrs[M];
pair<string, string> queries[M];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        addWord(s, +1);
    }

    
    for (int i = 0; i < m; i++) {
        string p, q;
        cin >> p >> q;
        addWord(q, 0);
        queries[i] = {p, q};
    }

    build();
    for (int i = 1; i <= numberOfNodes; i++) {
        for (int x = 0; x < 4; x++) {
            int nxt = node(i).to[x];
            if (nxt)
                g1.e[i].push_back(nxt);
        }
        if (node(i).link) 
            g2.e[node(i).link].push_back(i);
    }    
    g1.dfs(1, 1);
    g2.dfs(1, 1);
    
    for (int i = 0; i < m; i++) {
        auto [p, q] = queries[i];
        if (!checkWord(p)) continue;
        int u = root, v = root;
        for (char c : p) u = getNext(u, c);
        for (char c : q) v = getNext(v, c);
        qrs[g1.tin[u] - 1].push_back({g2.tin[v], g2.tout[v], -1, i});
        qrs[g1.tout[u]].push_back({g2.tin[v], g2.tout[v], +1, i});
    }

    for (int i = 0; i < M; i++) {
        int v = g1.ord[i];
        if (v) 
            fnw.update(g2.tin[v], node(v).term);
        for (auto q : qrs[i]) {
            int val = fnw.get(q.l, q.r);
            res[q.inx] += q.mul * val;
        }
    }
    for (int i = 0; i < m; i++)
        cout << res[i] << '\n';
}

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