제출 #1081665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081665		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	922 ms	551344 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40