oj.uz

Submission #847035

# Submission time Handle Problem Language Result Execution time Memory
847035 2023-09-09T02:31:26 Z x0r Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 220 ms 120932 KB 
#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define pb push_back
#define pss pair < string, string >

using namespace std;

const int NMAX = 1E5;
const ll MOD = 1E9 + 7;
const ll BASE = 2309;

using vl = vector < int >;

int n, m, root[NMAX + 3], res[NMAX + 3];

string rev[NMAX + 3], b[NMAX + 3];

pair < string, vl > s[NMAX + 3];

pair < pss, int > a[NMAX + 3];

map < char, int > charv;

struct Node {
    int nxt[4], cnt;
    Node() {
        cnt = 0;
        for (int i = 0; i < 4; i++) nxt[i] = -1;
    }
};

vector < Node > trie;

void Add() {
    trie.pb(Node());
    trie.back().cnt = 0;
}

void build(int id, int prev) {
    Add(); root[id] = trie.size() - 1;
    int cur = root[id];
    if (prev != -1) for (int i = 0; i < 4; i++) trie[cur].nxt[i] = trie[prev].nxt[i];
    trie[cur].cnt = trie[prev].cnt + 1;
    string news = "";
    for (auto c : rev[id]) {
        Add();
        trie[cur].nxt[charv[c]] = trie.size() - 1;
        cur = trie[cur].nxt[charv[c]];
        if (prev != -1) prev = trie[prev].nxt[charv[c]];
        if (prev != -1) trie[cur].cnt = trie[prev].cnt + 1;
        else trie[cur].cnt = 1;
        news += c;
        //cout << id << " " << news << " " << cur << " " << trie[cur].cnt << '\n';
        if (prev != -1) for (int i = 0; i < 4; i++) trie[cur].nxt[i] = trie[prev].nxt[i];
    }
}

int calc(int cur, const string &a) {
    for (auto c : a) {
        if (trie[cur].nxt[charv[c]] == -1) return 0;
        cur = trie[cur].nxt[charv[c]];
    }
    return trie[cur].cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("RNA.inp", "r", stdin);
    //freopen("RNA.out", "w", stdout);
    charv['A'] = 0; charv['G'] = 1; charv['C'] = 2; charv['U'] = 3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i].fi;
        s[i].se.pb(0);
        for (auto c : s[i].fi) s[i].se.pb((s[i].se.back() * BASE + c));
        b[i] = "";
    }
    sort(s + 1, s + n + 1, [&](const pair < string, vl > &x, const pair < string, vl > &y) {
        int l = 1, r = min(x.fi.size(), y.fi.size()), mid, ans = 0;
        while (l <= r) {
            mid = (l + r) / 2;
            if (x.se[mid] == y.se[mid]) {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if (ans == min(x.fi.size(), y.fi.size())) return x.fi.size() < y.fi.size();
        return x.fi[ans] < y.fi[ans];
    });
    for (int i = 1; i <= n; i++) {
        rev[i] = s[i].fi;
        reverse(rev[i].begin(), rev[i].end());
    }
    Add(); root[0] = 0;
    for (int i = 1; i <= n; i++) build(i, root[i - 1]);
    //for (int i = 1; i <= n; i++) cout << rev[i] << " " << calc(root[i], "A") << '\n';
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi.fi >> a[i].fi.se;
        a[i].se = i;
        reverse(a[i].fi.se.begin(), a[i].fi.se.end());
    }
    /*sort(a + 1, a + m + 1, [&](const pair < pss, int > &x, const pair < pss, int > &y) {
        return x.fi.fi.size() < y.fi.fi.size();
    });*/
    for (int i = 1; i <= m; i++) {
        /*cout << i << '\n';
        for (int j = 1; j <= n; j++) cout << b[j] << " ";
        cout << '\n';*/
        string &pre = a[i].fi.fi; int prelen = a[i].fi.fi.size();
        int l = 1, r = n, mid, ans = -1;
        while (l <= r) {
            mid = (l + r) / 2;
            if (s[mid].fi >= a[i].fi.fi) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if (ans == -1 || s[ans].fi.size() < prelen || s[ans].fi.substr(0, prelen) != pre) continue;
        res[a[i].se] -= calc(root[ans - 1], a[i].fi.se);
        l = ans, r = n;
         while (l <= r) {
            mid = (l + r) / 2;
            if (s[mid].fi.size() >= prelen && s[mid].fi.substr(0, prelen) == pre) {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        res[a[i].se] += calc(root[ans], a[i].fi.se);
    }
    for (int i = 1; i <= m; i++) cout << res[i] << '\n';
}

Compilation message

selling_rna.cpp: In lambda function:
selling_rna.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   92 |         if (ans == min(x.fi.size(), y.fi.size())) return x.fi.size() < y.fi.size();
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:124:43: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |         if (ans == -1 || s[ans].fi.size() < prelen || s[ans].fi.substr(0, prelen) != pre) continue;
      |                          ~~~~~~~~~~~~~~~~~^~~~~~~~
selling_rna.cpp:129:34: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |             if (s[mid].fi.size() >= prelen && s[mid].fi.substr(0, prelen) == pre) {
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 76492 KB Output is correct
2 Correct 77 ms 76712 KB Output is correct
3 Correct 109 ms 76708 KB Output is correct
4 Correct 112 ms 76988 KB Output is correct
5 Correct 75 ms 70836 KB Output is correct
6 Correct 72 ms 69804 KB Output is correct
7 Correct 80 ms 72116 KB Output is correct
8 Correct 105 ms 77988 KB Output is correct
9 Correct 100 ms 76876 KB Output is correct
10 Correct 78 ms 74664 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 26824 KB Output is correct
2 Correct 31 ms 23488 KB Output is correct
3 Correct 37 ms 26616 KB Output is correct
4 Correct 33 ms 27008 KB Output is correct
5 Correct 31 ms 23460 KB Output is correct
6 Correct 42 ms 26828 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19280 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19272 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 71 ms 76492 KB Output is correct
9 Correct 77 ms 76712 KB Output is correct
10 Correct 109 ms 76708 KB Output is correct
11 Correct 112 ms 76988 KB Output is correct
12 Correct 75 ms 70836 KB Output is correct
13 Correct 72 ms 69804 KB Output is correct
14 Correct 80 ms 72116 KB Output is correct
15 Correct 105 ms 77988 KB Output is correct
16 Correct 100 ms 76876 KB Output is correct
17 Correct 78 ms 74664 KB Output is correct
18 Correct 42 ms 26824 KB Output is correct
19 Correct 31 ms 23488 KB Output is correct
20 Correct 37 ms 26616 KB Output is correct
21 Correct 33 ms 27008 KB Output is correct
22 Correct 31 ms 23460 KB Output is correct
23 Correct 42 ms 26828 KB Output is correct
24 Correct 94 ms 76444 KB Output is correct
25 Correct 117 ms 77980 KB Output is correct
26 Correct 86 ms 76984 KB Output is correct
27 Correct 136 ms 76648 KB Output is correct
28 Correct 220 ms 120932 KB Output is correct
29 Correct 149 ms 68780 KB Output is correct