oj.uz

Submission #434338

# Submission time Handle Problem Language Result Execution time Memory
434338 2021-06-21T02:13:07 Z Mike4235 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 344 ms 203504 KB 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

struct Node1{
    int child[4];
    int l, r;
};

struct Node2{
    int child[4];
    vector<int> id;
};

vector<Node1> Trie1;
vector<Node2> Trie2;

void init1(int i) {
    Node1 tmp;
    memset(tmp.child, -1, sizeof(tmp.child));
    tmp.l = i;
    Trie1.push_back(tmp);
}

void init2() {
    Node2 tmp;
    memset(tmp.child, -1, sizeof(tmp.child));
    Trie2.push_back(tmp);
}

void add(string& s, int id) {
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie1[pos].child[t] == -1) {
            Trie1[pos].child[t] = sz(Trie1);
            init1(id);
        }

        pos = Trie1[pos].child[t];
        Trie1[pos].r = id;
    }

    reverse(s.begin(), s.end());
    pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie2[pos].child[t] == -1) {
            Trie2[pos].child[t] = sz(Trie2);
            init2();
        }

        pos = Trie2[pos].child[t];
        Trie2[pos].id.push_back(id);
    }
}

pii range(string& s) {
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie1[pos].child[t] == -1) return {0, 0};
        pos = Trie1[pos].child[t];
    }

    return {Trie1[pos].l, Trie1[pos].r};
}

int n, q;
string s[100005];

int get(string& s, pii p) {
    reverse(s.begin(), s.end());
    int pos = 0;
    for (auto i : s) {
        int t;
        if (i == 'A') t = 0;
        else if (i == 'U') t = 1;
        else if (i == 'G') t = 2;
        else t = 3;

        if (Trie2[pos].child[t] == -1) return 0;
        pos = Trie2[pos].child[t];
    }

    return upper_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.second) - lower_bound(Trie2[pos].id.begin(), Trie2[pos].id.end(), p.first);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    init1(0); init2();

    cin >> n >> q;
    for1(i,1,n) cin >> s[i];
    sort(s + 1, s + n + 1);
    for1(i,1,n) add(s[i], i);

    while(q--) {
        string pre, suf;
        cin >> pre >> suf;

        auto p = range(pre);
        cout << get(suf, p) << "\n";
    }
    
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 179008 KB Output is correct
2 Correct 344 ms 170184 KB Output is correct
3 Correct 199 ms 122068 KB Output is correct
4 Correct 191 ms 118788 KB Output is correct
5 Correct 339 ms 203404 KB Output is correct
6 Correct 330 ms 203504 KB Output is correct
7 Correct 67 ms 26376 KB Output is correct
8 Correct 271 ms 142740 KB Output is correct
9 Correct 233 ms 125188 KB Output is correct
10 Correct 210 ms 118848 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5088 KB Output is correct
2 Correct 25 ms 5352 KB Output is correct
3 Correct 29 ms 5348 KB Output is correct
4 Correct 22 ms 5020 KB Output is correct
5 Correct 25 ms 5228 KB Output is correct
6 Correct 30 ms 5280 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 3 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 334 ms 179008 KB Output is correct
9 Correct 344 ms 170184 KB Output is correct
10 Correct 199 ms 122068 KB Output is correct
11 Correct 191 ms 118788 KB Output is correct
12 Correct 339 ms 203404 KB Output is correct
13 Correct 330 ms 203504 KB Output is correct
14 Correct 67 ms 26376 KB Output is correct
15 Correct 271 ms 142740 KB Output is correct
16 Correct 233 ms 125188 KB Output is correct
17 Correct 210 ms 118848 KB Output is correct
18 Correct 31 ms 5088 KB Output is correct
19 Correct 25 ms 5352 KB Output is correct
20 Correct 29 ms 5348 KB Output is correct
21 Correct 22 ms 5020 KB Output is correct
22 Correct 25 ms 5228 KB Output is correct
23 Correct 30 ms 5280 KB Output is correct
24 Correct 336 ms 156780 KB Output is correct
25 Correct 338 ms 156784 KB Output is correct
26 Correct 320 ms 156744 KB Output is correct
27 Correct 192 ms 120404 KB Output is correct
28 Correct 219 ms 47000 KB Output is correct
29 Correct 97 ms 16728 KB Output is correct