oj.uz

Submission #1081665

# Submission time Handle Problem Language Result Execution time Memory
1081665 2024-08-30T08:57:29 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 922 ms 551344 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    int start, end;

    TrieNode() : start(-1), end(-1) {}
};

class Trie {
public:
    TrieNode* root;
    int timer;

    Trie() {
        root = new TrieNode();
        timer = 0;
    }

    TrieNode* insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        return node;
    }

    void eulerTour(TrieNode* node) {
        node->start = timer++;
        for (auto& child : node->children) {
            eulerTour(child.second);
        }
        node->end = timer - 1;
    }

    void build(const vector<string>& words) {
        for (const string& word : words) {
            insert(word);
        }
        eulerTour(root);
    }
};

class FenwickTree {
public:
    vector<int> tree;
    int size;

    FenwickTree(int n) : size(n) {
        tree.resize(n + 1, 0);
    }

    void update(int index, int delta) {
        while (index <= size) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }

    int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
};

struct Event {
    int x, type, y1, y2, queryIndex;

    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> rna_sequences(n);
    vector<pair<string, string>> queries(m);

    for (int i = 0; i < n; ++i) {
        cin >> rna_sequences[i];
    }

    for (int i = 0; i < m; ++i) {
        cin >> queries[i].first >> queries[i].second;
    }

    Trie prefixTrie, suffixTrie;
    prefixTrie.build(rna_sequences);

    vector<string> reversed_rna_sequences(n);
    for (int i = 0; i < n; ++i) {
        reversed_rna_sequences[i] = string(rna_sequences[i].rbegin(), rna_sequences[i].rend());
    }
    suffixTrie.build(reversed_rna_sequences);

    vector<Event> events;
    vector<int> results(m, 0);

    vector<pair<int, int>> points;
    for (int i = 0; i < n; ++i) {
        TrieNode* pNode = prefixTrie.insert(rna_sequences[i]);
        TrieNode* sNode = suffixTrie.insert(reversed_rna_sequences[i]);
        points.emplace_back(pNode->start, sNode->start);
    }

    for (int i = 0; i < m; ++i) {
        TrieNode* pNode = prefixTrie.insert(queries[i].first);
        TrieNode* sNode = suffixTrie.insert(string(queries[i].second.rbegin(), queries[i].second.rend()));

        if (pNode->start == -1 || sNode->start == -1) {
            continue;
        }

        events.push_back({pNode->start, 1, sNode->start, sNode->end, i});
        events.push_back({pNode->end + 1, 2, sNode->start, sNode->end, i});
    }

    for (const auto& p : points) {
        events.push_back({p.first, 3, p.second, p.second, -1});
    }

    sort(events.begin(), events.end());

    FenwickTree bit(suffixTrie.timer);

    for (const auto& event : events) {
        if (event.type == 1) {
            results[event.queryIndex] -= bit.rangeQuery(event.y1, event.y2);
        } else if (event.type == 2) {
            results[event.queryIndex] += bit.rangeQuery(event.y1, event.y2);
        } else if (event.type == 3) {
            bit.update(event.y1, 1);
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << results[i] << endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 447896 KB Output is correct
2 Correct 922 ms 424368 KB Output is correct
3 Correct 528 ms 434328 KB Output is correct
4 Correct 516 ms 413604 KB Output is correct
5 Correct 555 ms 543048 KB Output is correct
6 Correct 536 ms 551344 KB Output is correct
7 Correct 250 ms 11304 KB Output is correct
8 Correct 887 ms 325220 KB Output is correct
9 Correct 533 ms 274348 KB Output is correct
10 Correct 400 ms 264320 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12740 KB Output is correct
2 Correct 57 ms 8008 KB Output is correct
3 Correct 67 ms 9228 KB Output is correct
4 Correct 57 ms 7680 KB Output is correct
5 Correct 56 ms 8264 KB Output is correct
6 Correct 70 ms 9224 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 528 ms 447896 KB Output is correct
9 Correct 922 ms 424368 KB Output is correct
10 Correct 528 ms 434328 KB Output is correct
11 Correct 516 ms 413604 KB Output is correct
12 Correct 555 ms 543048 KB Output is correct
13 Correct 536 ms 551344 KB Output is correct
14 Correct 250 ms 11304 KB Output is correct
15 Correct 887 ms 325220 KB Output is correct
16 Correct 533 ms 274348 KB Output is correct
17 Correct 400 ms 264320 KB Output is correct
18 Correct 83 ms 12740 KB Output is correct
19 Correct 57 ms 8008 KB Output is correct
20 Correct 67 ms 9228 KB Output is correct
21 Correct 57 ms 7680 KB Output is correct
22 Correct 56 ms 8264 KB Output is correct
23 Correct 70 ms 9224 KB Output is correct
24 Correct 753 ms 368988 KB Output is correct
25 Correct 592 ms 372420 KB Output is correct
26 Correct 518 ms 363600 KB Output is correct
27 Correct 826 ms 358380 KB Output is correct
28 Correct 410 ms 78636 KB Output is correct
29 Correct 268 ms 24900 KB Output is correct