oj.uz

답안 #1070420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070420 2024-08-22T14:04:50 Z windowwife Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 308 ms 557196 KB 
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 3e6 + 2, mod = 998244353;
int n, res, numnode, m, ok;
string s[maxn], p, q;
struct Node
{
    int child[26];
    int l, r;
    vector<int> v;
}node[maxn];
struct PrefixTrie
{
    void add (int idx, string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0)
            {
                cur = node[cur].child[c - 'A'] = ++numnode;
                node[cur].l = node[cur].r = idx;
            }
            else
            {
                cur = node[cur].child[c - 'A'];
                node[cur].r = idx;
            }
        }
    }
    pair<int, int> find (string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) return {0, 0};
            cur = node[cur].child[c - 'A'];
        }
        return {node[cur].l, node[cur].r};
    }
}ptrie;
struct SuffixTrie
{
    void add (int idx, string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) cur = node[cur].child[c - 'A'] = ++numnode;
            else cur = node[cur].child[c - 'A'];
            node[cur].v.push_back(idx);
        }
    }
    int find (string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) return {};
            cur = node[cur].child[c - 'A'];
        }
        return cur;
    }
}strie;
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) ptrie.add(i, s[i]);
    for (int i = 1; i <= n; i++)
    {
        reverse(s[i].begin(), s[i].end());
        strie.add(i, s[i]);
    }
    while (m--)
    {
        cin >> p >> q;
        reverse(q.begin(), q.end());
        auto [L, R] = ptrie.find(p);
        ok = strie.find(q);
        if (L == 0 || node[ok].v.empty())
        {
            cout << 0 << '\n';
            continue;
        }
        if (node[ok].v.back() != n + 1) node[ok].v.push_back(n + 1);
        cout << upper_bound(node[ok].v.begin(), node[ok].v.end(), R) - lower_bound(node[ok].v.begin(), node[ok].v.end(), L) << '\n';
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 493556 KB Output is correct
2 Correct 178 ms 493392 KB Output is correct
3 Correct 173 ms 493396 KB Output is correct
4 Correct 176 ms 493396 KB Output is correct
5 Correct 179 ms 493392 KB Output is correct
6 Correct 175 ms 493392 KB Output is correct
7 Correct 175 ms 493564 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 557196 KB Output is correct
2 Correct 277 ms 553812 KB Output is correct
3 Correct 228 ms 506536 KB Output is correct
4 Correct 220 ms 506452 KB Output is correct
5 Correct 292 ms 533120 KB Output is correct
6 Correct 284 ms 533648 KB Output is correct
7 Correct 215 ms 503380 KB Output is correct
8 Correct 302 ms 523776 KB Output is correct
9 Correct 276 ms 519824 KB Output is correct
10 Correct 250 ms 519644 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 494416 KB Output is correct
2 Correct 189 ms 494160 KB Output is correct
3 Correct 185 ms 494144 KB Output is correct
4 Correct 200 ms 494144 KB Output is correct
5 Correct 184 ms 494116 KB Output is correct
6 Correct 193 ms 494292 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 493556 KB Output is correct
2 Correct 178 ms 493392 KB Output is correct
3 Correct 173 ms 493396 KB Output is correct
4 Correct 176 ms 493396 KB Output is correct
5 Correct 179 ms 493392 KB Output is correct
6 Correct 175 ms 493392 KB Output is correct
7 Correct 175 ms 493564 KB Output is correct
8 Correct 308 ms 557196 KB Output is correct
9 Correct 277 ms 553812 KB Output is correct
10 Correct 228 ms 506536 KB Output is correct
11 Correct 220 ms 506452 KB Output is correct
12 Correct 292 ms 533120 KB Output is correct
13 Correct 284 ms 533648 KB Output is correct
14 Correct 215 ms 503380 KB Output is correct
15 Correct 302 ms 523776 KB Output is correct
16 Correct 276 ms 519824 KB Output is correct
17 Correct 250 ms 519644 KB Output is correct
18 Correct 190 ms 494416 KB Output is correct
19 Correct 189 ms 494160 KB Output is correct
20 Correct 185 ms 494144 KB Output is correct
21 Correct 200 ms 494144 KB Output is correct
22 Correct 184 ms 494116 KB Output is correct
23 Correct 193 ms 494292 KB Output is correct
24 Correct 289 ms 546176 KB Output is correct
25 Correct 290 ms 546388 KB Output is correct
26 Correct 293 ms 545500 KB Output is correct
27 Correct 245 ms 505948 KB Output is correct
28 Correct 297 ms 511328 KB Output is correct
29 Correct 229 ms 502120 KB Output is correct