Submission #375886

#	Time	Username	Problem	Language	Result	Execution time	Memory
375886		mihai145	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	352 ms	199240 KiB

selling_rna

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int NMAX = 1e5;
const int QMAX = 1e5;

struct Node {
    Node* sons[4];
    vector <int> wordList;
    pair <int, int> wordRange;

    Node() {
        for(int i = 0; i < 4; i++) {
            sons[i] = NULL;
        }
    }
};

int N, Q;

string s;
Node *pref = new Node, *suf = new Node;

int GetSon(char s) {
    if(s == 'A') {
        return 0;
    } else if(s == 'G') {
        return 1;
    } else if(s == 'C') {
        return 2;
    }
    return 3;
}

void InsertPref(Node* node, int index, int id) {
    if(index == (int)s.size()) {
        node-> wordList.push_back(id);
        return;
    }

    int son = GetSon(s[index]);
    if(node-> sons[son] == NULL) {
        node-> sons[son] = new Node;
    }

    InsertPref(node-> sons[son], index + 1, id);
}

void InsertSuf(Node* node, int index, int id) {
    if(index == -1) {
        node-> wordList.push_back(id);
        return;
    }

    int son = GetSon(s[index]);
    if(node-> sons[son] == NULL) {
        node-> sons[son] = new Node;
    }

    InsertSuf(node-> sons[son], index - 1, id);
}

string pr, sf;
vector<int> wordsWithPref, wordsWithSuf;

vector <int> prefOrder;
vector <int> sufOrder;

void DfsPref(Node* root) {
    if(root == NULL) {
        return ;
    }

    root->wordRange.first = (int)prefOrder.size() + 1;
    for(int word : root-> wordList) {
        prefOrder.push_back(word);
    }

    for(int j = 0; j < 4; j++) {
        DfsPref(root-> sons[j]);
    }

    root->wordRange.second = (int)prefOrder.size();
}

void DfsSuf(Node* root) {
    if(root == NULL) {
        return ;
    }

    root->wordRange.first = (int)sufOrder.size() + 1;
    for(int word : root-> wordList) {
        sufOrder.push_back(word);
    }

    for(int j = 0; j < 4; j++) {
        DfsSuf(root-> sons[j]);
    }

    root->wordRange.second = (int)sufOrder.size();
}

pair<int, int> GetRangePref(Node* root, int index) {
    if(root == NULL) {
        return {-1, -1};
    }

    if(index == (int)pr.size()) {
        return root-> wordRange;
    }

    int son = GetSon(pr[index]);
    return GetRangePref(root-> sons[son], index + 1);
}

pair<int, int> GetRangeSuf(Node* root, int index) {
    if(root == NULL) {
        return {-1, -1};
    }

    if(index == -1) {
        return root-> wordRange;
    }

    int son = GetSon(sf[index]);
    return GetRangeSuf(root-> sons[son], index - 1);
}


int posSuf[NMAX + 2], matchLine[NMAX + 2];

struct LineQuery {
    int l, r, ind;
};
vector<LineQuery> lineQueries[NMAX + 2];
int k, ansLine[2 * QMAX + 2];

pair <int, int> qrl[QMAX + 2];
int ans[QMAX + 2];

int aib[NMAX + 2];

inline int LSB(int x) {
    return x & (-x);
}

void Update(int pos) {
    for(int i = pos; i <= N; i += LSB(i)) {
        aib[i]++;
    }
}

int Query(int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= LSB(i)) {
        ans += aib[i];
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for(int i = 1; i <= N; i++) {
        cin >> s;

        InsertPref(pref, 0, i);
        InsertSuf(suf, (int)s.size() - 1, i);
    }

    DfsPref(pref);
    DfsSuf(suf);

    for(int i = 1; i <= Q; i++) {
        cin >> pr >> sf;

        pair <int, int> rangePref = GetRangePref(pref, 0);
        pair <int, int> rangeSuf = GetRangeSuf(suf, (int)sf.size() - 1);

        if(rangePref.first == -1 || rangeSuf.first == -1 || (rangePref.first > rangePref.second) || (rangeSuf.first > rangeSuf.second)) {
            ans[i] = 0;
        } else {
            ++k;
            lineQueries[rangePref.second].push_back({rangeSuf.first, rangeSuf.second, k});

            ++k;
            lineQueries[rangePref.first - 1].push_back({rangeSuf.first, rangeSuf.second, k});

            qrl[i] = {k - 1, k};
        }
    }

    for(int i = 0; i < N; i++) {
        posSuf[sufOrder[i]] = i + 1;
    }
    for(int i = 0; i < N; i++) {
        matchLine[i + 1] = posSuf[prefOrder[i]];
    }

    for(int i = 1; i <= N; i++) {
        Update(matchLine[i]);
        for(LineQuery lq : lineQueries[i]) {
            ansLine[lq.ind] = Query(lq.r) - Query(lq.l - 1);
        }
    }

    for(int i = 1; i <= Q; i++) {
        if(qrl[i].first != 0) {
            ans[i] = ansLine[qrl[i].first] - ansLine[qrl[i].second];
        }
    }

    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

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