oj.uz

Submission #375886

# Submission time Handle Problem Language Result Execution time Memory
375886 2021-03-10T07:45:27 Z mihai145 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 352 ms 199240 KB 
#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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 161516 KB Output is correct
2 Correct 233 ms 153580 KB Output is correct
3 Correct 244 ms 159468 KB Output is correct
4 Correct 242 ms 152072 KB Output is correct
5 Correct 352 ms 196332 KB Output is correct
6 Correct 304 ms 199240 KB Output is correct
7 Correct 38 ms 8940 KB Output is correct
8 Correct 223 ms 121068 KB Output is correct
9 Correct 193 ms 102892 KB Output is correct
10 Correct 164 ms 97772 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7452 KB Output is correct
2 Correct 22 ms 6508 KB Output is correct
3 Correct 27 ms 7092 KB Output is correct
4 Correct 21 ms 6128 KB Output is correct
5 Correct 21 ms 6124 KB Output is correct
6 Correct 27 ms 6792 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 2 ms 2796 KB Output is correct
8 Correct 297 ms 161516 KB Output is correct
9 Correct 233 ms 153580 KB Output is correct
10 Correct 244 ms 159468 KB Output is correct
11 Correct 242 ms 152072 KB Output is correct
12 Correct 352 ms 196332 KB Output is correct
13 Correct 304 ms 199240 KB Output is correct
14 Correct 38 ms 8940 KB Output is correct
15 Correct 223 ms 121068 KB Output is correct
16 Correct 193 ms 102892 KB Output is correct
17 Correct 164 ms 97772 KB Output is correct
18 Correct 27 ms 7452 KB Output is correct
19 Correct 22 ms 6508 KB Output is correct
20 Correct 27 ms 7092 KB Output is correct
21 Correct 21 ms 6128 KB Output is correct
22 Correct 21 ms 6124 KB Output is correct
23 Correct 27 ms 6792 KB Output is correct
24 Correct 215 ms 134508 KB Output is correct
25 Correct 231 ms 136556 KB Output is correct
26 Correct 220 ms 132716 KB Output is correct
27 Correct 216 ms 132588 KB Output is correct
28 Correct 142 ms 33156 KB Output is correct
29 Correct 72 ms 14376 KB Output is correct