oj.uz

Submission #890435

# Submission time Handle Problem Language Result Execution time Memory
890435 2023-12-21T08:49:47 Z viwlesxq Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 769 ms 375460 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 998244353;

struct Trie {
    map<char, Trie*> children;
    vector<int> v;
    int pref;
    bool end;
    Trie() {
        pref = 0;
        end = false;
    }
};
void insert(Trie *root, string rna, int ind) {
    Trie *cur = root;
    for (int i = 0; i < size(rna); i++) {
        Trie *node = cur->children[rna[i]];
        if (!node) {
            node = new Trie();
            cur->children[rna[i]] = node;
        }
        cur = node;
        cur->pref++;
        cur->v.push_back(ind);
    }
    cur->end = true;
}
int get(Trie *root, string rna, int l, int r) {
    Trie *cur = root;
    for (int i = 0; i < size(rna); i++) {
        Trie *node = cur->children[rna[i]];
        if (!node) {
            return 0;
        }
        cur = node;
    }
    return (upper_bound(all(cur->v), r) - cur->v.begin()) - (lower_bound(all(cur->v), l) - cur->v.begin());
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    Trie *root = new Trie();
    int n, m;
    cin >> n >> m;
    string s[n];
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    sort(s, s + n);
    for (int i = 0; i < n; ++i) {
        reverse(all(s[i]));
        insert(root, s[i], i);
        reverse(all(s[i]));
    }
    while (m--) {
        string p, q;
        cin >> p >> q;
        reverse(all(q));
        int l = 0, r = n - 1;
        for (int i = 0; i < size(p); ++i) {
            int lo = l - 1, hi = r + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;
                if (size(s[mid]) < i + 1) {
                    lo = mid;
                } else {
                    if (s[mid][i] < p[i]) {
                        lo = mid;
                    } else {
                        hi = mid;
                    }
                }
            }
            int low = lo + 1;
            lo = l - 1, hi = r + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;
                if (size(s[mid]) < i + 1) {
                    lo = mid;
                } else {
                    if (s[mid][i] <= p[i]) {
                        lo = mid;
                    } else {
                        hi = mid;
                    }
                }
            }
            int high = hi - 1;
            l = low, r = high;
            if (l > r) {
                break;
            }
        }
        if (l > r) {
            cout << 0 << '\n';
            continue;
        }
        cout << get(root, q, l, r) << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 375460 KB Output is correct
2 Correct 640 ms 355944 KB Output is correct
3 Correct 61 ms 29268 KB Output is correct
4 Correct 66 ms 28000 KB Output is correct
5 Correct 202 ms 233080 KB Output is correct
6 Correct 192 ms 236368 KB Output is correct
7 Correct 273 ms 23380 KB Output is correct
8 Correct 368 ms 154452 KB Output is correct
9 Correct 401 ms 134256 KB Output is correct
10 Correct 188 ms 126800 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3664 KB Output is correct
2 Correct 28 ms 3676 KB Output is correct
3 Correct 33 ms 3648 KB Output is correct
4 Correct 34 ms 3020 KB Output is correct
5 Correct 23 ms 2908 KB Output is correct
6 Correct 30 ms 3420 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 513 ms 375460 KB Output is correct
9 Correct 640 ms 355944 KB Output is correct
10 Correct 61 ms 29268 KB Output is correct
11 Correct 66 ms 28000 KB Output is correct
12 Correct 202 ms 233080 KB Output is correct
13 Correct 192 ms 236368 KB Output is correct
14 Correct 273 ms 23380 KB Output is correct
15 Correct 368 ms 154452 KB Output is correct
16 Correct 401 ms 134256 KB Output is correct
17 Correct 188 ms 126800 KB Output is correct
18 Correct 32 ms 3664 KB Output is correct
19 Correct 28 ms 3676 KB Output is correct
20 Correct 33 ms 3648 KB Output is correct
21 Correct 34 ms 3020 KB Output is correct
22 Correct 23 ms 2908 KB Output is correct
23 Correct 30 ms 3420 KB Output is correct
24 Correct 755 ms 309108 KB Output is correct
25 Correct 671 ms 309232 KB Output is correct
26 Correct 769 ms 305744 KB Output is correct
27 Correct 74 ms 28240 KB Output is correct
28 Correct 710 ms 67520 KB Output is correct
29 Correct 251 ms 16756 KB Output is correct