oj.uz

Submission #847025

# Submission time Handle Problem Language Result Execution time Memory
847025 2023-09-09T02:17:31 Z x0r Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 80788 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, [&](pair < string, vl > &x, 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, [&](pair < pss, int > &x, pair < pss, int > &y) {
        return x.fi.fi.size() < y.fi.fi.size();
    });
    for (int i = 1; i <= m; i++) {
        if (b[1].size() < a[i].fi.fi.size()) {
            for (int j = 1; j <= n; j++)
                while (b[j].size() < s[j].fi.size() && b[j].size() < a[i].fi.fi.size()) b[j] += s[j].fi[b[j].size()];
        }
        /*cout << i << '\n';
        for (int j = 1; j <= n; j++) cout << b[j] << " ";
        cout << '\n';*/
        int l = 1, r = n, mid, ans;
        while (l <= r) {
            mid = (l + r) / 2;
            if (b[mid] <= a[i].fi.fi) {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if (b[ans] != a[i].fi.fi) continue;
        res[a[i].se] = calc(root[ans], a[i].fi.se);
        l = 1, r = n;
        while (l <= r) {
            mid = (l + r) / 2;
            if (b[mid] >= a[i].fi.fi) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        res[a[i].se] -= calc(root[ans - 1], 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:128:28: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         res[a[i].se] = calc(root[ans], a[i].fi.se);
      |                        ~~~~^~~~~~~~~~~~~~~~~~~~~~~

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 19052 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 78024 KB Output is correct
2 Correct 145 ms 79520 KB Output is correct
3 Correct 117 ms 75700 KB Output is correct
4 Correct 146 ms 77060 KB Output is correct
5 Correct 137 ms 69560 KB Output is correct
6 Correct 146 ms 71612 KB Output is correct
7 Correct 113 ms 73672 KB Output is correct
8 Correct 106 ms 80788 KB Output is correct
9 Correct 126 ms 79952 KB Output is correct
10 Correct 86 ms 76100 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27608 KB Output is correct
2 Correct 1362 ms 23488 KB Output is correct
3 Execution timed out 1539 ms 28016 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19052 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 87 ms 78024 KB Output is correct
9 Correct 145 ms 79520 KB Output is correct
10 Correct 117 ms 75700 KB Output is correct
11 Correct 146 ms 77060 KB Output is correct
12 Correct 137 ms 69560 KB Output is correct
13 Correct 146 ms 71612 KB Output is correct
14 Correct 113 ms 73672 KB Output is correct
15 Correct 106 ms 80788 KB Output is correct
16 Correct 126 ms 79952 KB Output is correct
17 Correct 86 ms 76100 KB Output is correct
18 Correct 40 ms 27608 KB Output is correct
19 Correct 1362 ms 23488 KB Output is correct
20 Execution timed out 1539 ms 28016 KB Time limit exceeded
21 Halted 0 ms 0 KB -