oj.uz

Submission #847031

# Submission time Handle Problem Language Result Execution time Memory
847031 2023-09-09T02:24:36 Z x0r Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 80796 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;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        res[a[i].se] -= calc(root[ans - 1], a[i].fi.se);
        if (b[ans] != a[i].fi.fi) continue;
        l = ans, r = n;
         while (l <= r) {
            mid = (l + r) / 2;
            if (b[mid] <= a[i].fi.fi) {
                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:118:32: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |         int l = 1, r = n, mid, ans;
      |                                ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 79004 KB Output is correct
2 Correct 151 ms 79484 KB Output is correct
3 Correct 124 ms 76644 KB Output is correct
4 Correct 133 ms 77240 KB Output is correct
5 Correct 139 ms 70068 KB Output is correct
6 Correct 143 ms 70320 KB Output is correct
7 Correct 96 ms 72108 KB Output is correct
8 Correct 111 ms 80532 KB Output is correct
9 Correct 121 ms 80796 KB Output is correct
10 Correct 85 ms 75932 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27852 KB Output is correct
2 Correct 994 ms 23484 KB Output is correct
3 Execution timed out 1531 ms 27084 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 19032 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19032 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 86 ms 79004 KB Output is correct
9 Correct 151 ms 79484 KB Output is correct
10 Correct 124 ms 76644 KB Output is correct
11 Correct 133 ms 77240 KB Output is correct
12 Correct 139 ms 70068 KB Output is correct
13 Correct 143 ms 70320 KB Output is correct
14 Correct 96 ms 72108 KB Output is correct
15 Correct 111 ms 80532 KB Output is correct
16 Correct 121 ms 80796 KB Output is correct
17 Correct 85 ms 75932 KB Output is correct
18 Correct 40 ms 27852 KB Output is correct
19 Correct 994 ms 23484 KB Output is correct
20 Execution timed out 1531 ms 27084 KB Time limit exceeded
21 Halted 0 ms 0 KB -