oj.uz

Submission #396861

# Submission time Handle Problem Language Result Execution time Memory
396861 2021-04-30T20:08:40 Z Osama_Alkhodairy Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 469 ms 537524 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 2000001;

int n, m, trie[2][4 * N][4], cnt[2], mn[4 * N], mx[4 * N];
vector <int> f[4 * N];
vector <string> a;

int c(char c){
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    if(c == 'U') return 3;
    assert(false);
}
void add(string &s, int idx, int tr){
    int cur = 0;
    for(auto &i : s){
        if(trie[tr][cur][c(i)] == -1){
            trie[tr][cur][c(i)] = ++cnt[tr];
        }
        cur = trie[tr][cur][c(i)];
        if(tr == 0){
            if(mn[cur] == -1) mn[cur] = idx;
            mx[cur] = idx;
        }
        else{
            f[cur].push_back(idx);
        }
    }
}
pair <int, int> query1(string &s){
    int cur = 0;
    for(auto &i : s){
        if(trie[0][cur][c(i)] == -1){
            return make_pair(-1, -1);
        }
        cur = trie[0][cur][c(i)];
    }
    return make_pair(mn[cur], mx[cur]);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(trie, -1, sizeof trie);
    memset(mn, -1, sizeof mn);
    cin >> n >> m;
    a.resize(n);
    for(auto &i : a) cin >> i;
    sort(a.begin(), a.end());
    for(int i = 0 ; i < n ; i++){
        add(a[i], i, 0);
        reverse(a[i].begin(), a[i].end());
        add(a[i], i, 1);
        reverse(a[i].begin(), a[i].end());
    }
    for(int i = 0 ; i < m ; i++){
        string l, r;
        cin >> l >> r;
        reverse(r.begin(), r.end());
        auto q1 = query1(l);
        int cur = 0;
        for(auto &i : r){
            if(trie[1][cur][c(i)] == -1){
                q1 = make_pair(-1, -1);
                break;
            }
            cur = trie[1][cur][c(i)];
        }
        if(q1.first == -1){
            cout << "0\n";
            continue;
        }
        auto &q2 = f[cur];
        cout << upper_bound(q2.begin(), q2.end(), q1.second) - lower_bound(q2.begin(), q2.end(), q1.first) << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 469960 KB Output is correct
2 Correct 225 ms 469936 KB Output is correct
3 Correct 222 ms 469984 KB Output is correct
4 Correct 227 ms 469956 KB Output is correct
5 Correct 242 ms 469916 KB Output is correct
6 Correct 227 ms 469956 KB Output is correct
7 Correct 218 ms 469908 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 537524 KB Output is correct
2 Correct 394 ms 534468 KB Output is correct
3 Correct 327 ms 494816 KB Output is correct
4 Correct 302 ms 494404 KB Output is correct
5 Correct 366 ms 516832 KB Output is correct
6 Correct 365 ms 517568 KB Output is correct
7 Correct 270 ms 485472 KB Output is correct
8 Correct 366 ms 509116 KB Output is correct
9 Correct 347 ms 504600 KB Output is correct
10 Correct 329 ms 501740 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 472888 KB Output is correct
2 Correct 244 ms 471928 KB Output is correct
3 Correct 252 ms 472356 KB Output is correct
4 Correct 241 ms 472004 KB Output is correct
5 Correct 251 ms 472000 KB Output is correct
6 Correct 248 ms 472260 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 469960 KB Output is correct
2 Correct 225 ms 469936 KB Output is correct
3 Correct 222 ms 469984 KB Output is correct
4 Correct 227 ms 469956 KB Output is correct
5 Correct 242 ms 469916 KB Output is correct
6 Correct 227 ms 469956 KB Output is correct
7 Correct 218 ms 469908 KB Output is correct
8 Correct 462 ms 537524 KB Output is correct
9 Correct 394 ms 534468 KB Output is correct
10 Correct 327 ms 494816 KB Output is correct
11 Correct 302 ms 494404 KB Output is correct
12 Correct 366 ms 516832 KB Output is correct
13 Correct 365 ms 517568 KB Output is correct
14 Correct 270 ms 485472 KB Output is correct
15 Correct 366 ms 509116 KB Output is correct
16 Correct 347 ms 504600 KB Output is correct
17 Correct 329 ms 501740 KB Output is correct
18 Correct 253 ms 472888 KB Output is correct
19 Correct 244 ms 471928 KB Output is correct
20 Correct 252 ms 472356 KB Output is correct
21 Correct 241 ms 472004 KB Output is correct
22 Correct 251 ms 472000 KB Output is correct
23 Correct 248 ms 472260 KB Output is correct
24 Correct 410 ms 527108 KB Output is correct
25 Correct 469 ms 527212 KB Output is correct
26 Correct 400 ms 526340 KB Output is correct
27 Correct 303 ms 493032 KB Output is correct
28 Correct 462 ms 495300 KB Output is correct
29 Correct 304 ms 481600 KB Output is correct