oj.uz

Submission #940055

# Submission time Handle Problem Language Result Execution time Memory
940055 2024-03-07T04:48:21 Z phoenix Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1151 ms 769044 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 537684 KB Output is correct
2 Correct 192 ms 538040 KB Output is correct
3 Correct 191 ms 537712 KB Output is correct
4 Correct 193 ms 537684 KB Output is correct
5 Correct 190 ms 537784 KB Output is correct
6 Correct 189 ms 537680 KB Output is correct
7 Correct 193 ms 538056 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 544700 KB Output is correct
2 Correct 262 ms 544724 KB Output is correct
3 Correct 1151 ms 769044 KB Output is correct
4 Correct 1028 ms 762796 KB Output is correct
5 Correct 898 ms 714636 KB Output is correct
6 Correct 860 ms 714832 KB Output is correct
7 Correct 260 ms 547924 KB Output is correct
8 Correct 530 ms 623540 KB Output is correct
9 Correct 526 ms 628680 KB Output is correct
10 Correct 331 ms 594516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 540896 KB Output is correct
2 Correct 219 ms 540112 KB Output is correct
3 Correct 211 ms 540040 KB Output is correct
4 Correct 225 ms 539704 KB Output is correct
5 Correct 212 ms 540176 KB Output is correct
6 Correct 209 ms 540240 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 537684 KB Output is correct
2 Correct 192 ms 538040 KB Output is correct
3 Correct 191 ms 537712 KB Output is correct
4 Correct 193 ms 537684 KB Output is correct
5 Correct 190 ms 537784 KB Output is correct
6 Correct 189 ms 537680 KB Output is correct
7 Correct 193 ms 538056 KB Output is correct
8 Correct 268 ms 544700 KB Output is correct
9 Correct 262 ms 544724 KB Output is correct
10 Correct 1151 ms 769044 KB Output is correct
11 Correct 1028 ms 762796 KB Output is correct
12 Correct 898 ms 714636 KB Output is correct
13 Correct 860 ms 714832 KB Output is correct
14 Correct 260 ms 547924 KB Output is correct
15 Correct 530 ms 623540 KB Output is correct
16 Correct 526 ms 628680 KB Output is correct
17 Correct 331 ms 594516 KB Output is correct
18 Correct 206 ms 540896 KB Output is correct
19 Correct 219 ms 540112 KB Output is correct
20 Correct 211 ms 540040 KB Output is correct
21 Correct 225 ms 539704 KB Output is correct
22 Correct 212 ms 540176 KB Output is correct
23 Correct 209 ms 540240 KB Output is correct
24 Correct 259 ms 546008 KB Output is correct
25 Correct 278 ms 547924 KB Output is correct
26 Correct 261 ms 545240 KB Output is correct
27 Correct 721 ms 690512 KB Output is correct
28 Correct 299 ms 550448 KB Output is correct
29 Correct 260 ms 546000 KB Output is correct