oj.uz

Submission #897460

# Submission time Handle Problem Language Result Execution time Memory
897460 2024-01-03T06:43:30 Z dwuy Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 215 ms 203300 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MX = 100005;
int n, q;
int ans[MX];
string a[MX];
tuple<string, string, int> queries[MX];

void nhap(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=q; i++){
        string p, q;
        cin >> p >> q;
        queries[i] = {p, q, i};
    }
}

int cv(char c){
    return c=='A'? 0 : c=='G'? 1 : c=='C'? 2 : c=='U'? 3 : -1;
}

struct Node{
    vector<int> id;
    Node *child[4];

    Node(){
        this->id.clear();
        for(int t=4; t--;) this->child[t] = NULL;
    }
};

Node *root = new Node();

void add(string s, int id){
    reverse(s.begin(), s.end());
    Node *cur = root;
    for(char c: s){
        int t = cv(c);
        if(cur->child[t] == NULL) cur->child[t] = new Node();
        cur = cur->child[t];
        cur->id.push_back(id);
    }
}

void solve(){
    sort(a+1, a+1+n);
    sort(queries+1, queries+1+q);

    for(int i=1; i<=n; i++) add(a[i], i);

    a[0] = "";
    a[n+1] = "~";
    for(int i=1; i<=q; i++){
        string pf, sf; int id;
        tie(pf, sf, id) = queries[i];
        reverse(sf.begin(), sf.end());
        Node *cur = root;
        for(char c: sf){
            int t = cv(c);
            if(cur->child[t] == NULL){
                ans[id] = -1;
                break;
            }
            cur = cur->child[t];
        }
        #define all(x) (x).begin(),(x).end()
        if(ans[id] == -1) ans[id] = 0;
        else {
            int fx = cur->id.size();
            for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
                int mid = (lo+hi)>>1;
                int p = cur->id[mid];
                if(a[p] >= pf) fx = mid, hi = mid - 1;
                else lo = mid + 1;
            }
            int fy = cur->id.size();
            for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
                int mid = (lo+hi)>>1;
                int p = cur->id[mid];
                if(a[p] > pf+"}") fy = mid , hi = mid - 1;
                else lo = mid + 1;
            }
            ans[id] = fy - fx;
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 203300 KB Output is correct
2 Correct 175 ms 193440 KB Output is correct
3 Correct 59 ms 30492 KB Output is correct
4 Correct 41 ms 30192 KB Output is correct
5 Correct 124 ms 130372 KB Output is correct
6 Correct 129 ms 132052 KB Output is correct
7 Correct 42 ms 30472 KB Output is correct
8 Correct 114 ms 95592 KB Output is correct
9 Correct 98 ms 84764 KB Output is correct
10 Correct 80 ms 77396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 11984 KB Output is correct
2 Correct 32 ms 12116 KB Output is correct
3 Correct 41 ms 12252 KB Output is correct
4 Correct 32 ms 11868 KB Output is correct
5 Correct 38 ms 11856 KB Output is correct
6 Correct 43 ms 11860 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 208 ms 203300 KB Output is correct
9 Correct 175 ms 193440 KB Output is correct
10 Correct 59 ms 30492 KB Output is correct
11 Correct 41 ms 30192 KB Output is correct
12 Correct 124 ms 130372 KB Output is correct
13 Correct 129 ms 132052 KB Output is correct
14 Correct 42 ms 30472 KB Output is correct
15 Correct 114 ms 95592 KB Output is correct
16 Correct 98 ms 84764 KB Output is correct
17 Correct 80 ms 77396 KB Output is correct
18 Correct 58 ms 11984 KB Output is correct
19 Correct 32 ms 12116 KB Output is correct
20 Correct 41 ms 12252 KB Output is correct
21 Correct 32 ms 11868 KB Output is correct
22 Correct 38 ms 11856 KB Output is correct
23 Correct 43 ms 11860 KB Output is correct
24 Correct 180 ms 169808 KB Output is correct
25 Correct 215 ms 170064 KB Output is correct
26 Correct 170 ms 167936 KB Output is correct
27 Correct 66 ms 30244 KB Output is correct
28 Correct 212 ms 48280 KB Output is correct
29 Correct 108 ms 19400 KB Output is correct