oj.uz

Submission #897464

# Submission time Handle Problem Language Result Execution time Memory
897464 2024-01-03T06:49:17 Z dwuy Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 42 ms 30040 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';
}
 
struct Node{
    vector<int> id;
    Node *child[30];
 
    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 10844 KB Output is correct
5 Correct 3 ms 10676 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 30040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 21932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
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 10844 KB Output is correct
5 Correct 3 ms 10676 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Runtime error 20 ms 30040 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -