oj.uz

Submission #897466

# Submission time Handle Problem Language Result Execution time Memory
897466 2024-01-03T06:50:43 Z dwuy Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 319 ms 598864 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=30; 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 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 598864 KB Output is correct
2 Correct 317 ms 569648 KB Output is correct
3 Correct 44 ms 30288 KB Output is correct
4 Correct 47 ms 29904 KB Output is correct
5 Correct 235 ms 376764 KB Output is correct
6 Correct 236 ms 382260 KB Output is correct
7 Correct 42 ms 28416 KB Output is correct
8 Correct 185 ms 237420 KB Output is correct
9 Correct 159 ms 205028 KB Output is correct
10 Correct 128 ms 193180 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11984 KB Output is correct
2 Correct 36 ms 13004 KB Output is correct
3 Correct 40 ms 12372 KB Output is correct
4 Correct 33 ms 11812 KB Output is correct
5 Correct 33 ms 12124 KB Output is correct
6 Correct 42 ms 12112 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 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 319 ms 598864 KB Output is correct
9 Correct 317 ms 569648 KB Output is correct
10 Correct 44 ms 30288 KB Output is correct
11 Correct 47 ms 29904 KB Output is correct
12 Correct 235 ms 376764 KB Output is correct
13 Correct 236 ms 382260 KB Output is correct
14 Correct 42 ms 28416 KB Output is correct
15 Correct 185 ms 237420 KB Output is correct
16 Correct 159 ms 205028 KB Output is correct
17 Correct 128 ms 193180 KB Output is correct
18 Correct 51 ms 11984 KB Output is correct
19 Correct 36 ms 13004 KB Output is correct
20 Correct 40 ms 12372 KB Output is correct
21 Correct 33 ms 11812 KB Output is correct
22 Correct 33 ms 12124 KB Output is correct
23 Correct 42 ms 12112 KB Output is correct
24 Correct 283 ms 493508 KB Output is correct
25 Correct 319 ms 493460 KB Output is correct
26 Correct 271 ms 487668 KB Output is correct
27 Correct 56 ms 30068 KB Output is correct
28 Correct 223 ms 87796 KB Output is correct
29 Correct 104 ms 17996 KB Output is correct