oj.uz

Submission #896985

# Submission time Handle Problem Language Result Execution time Memory
896985 2024-01-02T11:53:35 Z Aiperiii Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 401 ms 332116 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2e6;
struct Trie{
    vector <int> v;
    map <char,int> mp;
};
Trie t[N];
int cnt=0;
void insert(string s,int ind){
    int p=0;
    for(int i=0;i<s.size();i++){
        if(t[p].mp[s[i]]==0){
            cnt++;
            t[p].mp[s[i]]=cnt;
        }
        p=t[p].mp[s[i]];
        t[p].v.pb(ind);
    }
}
int get(string s,int l,int r){
    int p=0;
    for(int i=0;i<s.size();i++){
        p=t[p].mp[s[i]];
        if(p==0)return 0;
    }
    auto L=lower_bound(all(t[p].v),l)-t[p].v.begin();
    auto R=upper_bound(all(t[p].v),r)-t[p].v.begin();
    return R-L;
}
signed main(){
    int n,m;
    cin>>n>>m;
    vector <string> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(all(a));
    for(int i=0;i<n;i++){
        string x=a[i];reverse(all(x));
        insert(x,i);
    }
    for(int i=0;i<m;i++){
        string s,q;
        cin>>s>>q;
        auto it=lower_bound(all(a),s);
        int l=it-a.begin();
        s.back()++;
        it=lower_bound(all(a),s);
        int r=it-a.begin()-1;
        if(l>r){
            cout<<0<<"\n";
            continue;
        }
        reverse(all(q));
        cout<<get(q,l,r)<<"\n";
        
    }
}
/*
 
 1
 0 1
 2
 0 1
 3
 0
 4
 1
 5
 1
 */

Compilation message

selling_rna.cpp: In function 'void insert(std::string, long long int)':
selling_rna.cpp:17:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'long long int get(std::string, long long int, long long int)':
selling_rna.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 141136 KB Output is correct
2 Correct 29 ms 141276 KB Output is correct
3 Correct 28 ms 141324 KB Output is correct
4 Correct 33 ms 141136 KB Output is correct
5 Correct 28 ms 141304 KB Output is correct
6 Correct 28 ms 141276 KB Output is correct
7 Correct 28 ms 141348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 332116 KB Output is correct
2 Correct 319 ms 322388 KB Output is correct
3 Correct 146 ms 169296 KB Output is correct
4 Correct 148 ms 168536 KB Output is correct
5 Correct 219 ms 259928 KB Output is correct
6 Correct 244 ms 261800 KB Output is correct
7 Correct 176 ms 163884 KB Output is correct
8 Correct 310 ms 227604 KB Output is correct
9 Correct 276 ms 217428 KB Output is correct
10 Correct 203 ms 213432 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 144456 KB Output is correct
2 Correct 92 ms 144048 KB Output is correct
3 Correct 108 ms 144216 KB Output is correct
4 Correct 93 ms 143816 KB Output is correct
5 Correct 93 ms 143700 KB Output is correct
6 Correct 118 ms 144056 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 141136 KB Output is correct
2 Correct 29 ms 141276 KB Output is correct
3 Correct 28 ms 141324 KB Output is correct
4 Correct 33 ms 141136 KB Output is correct
5 Correct 28 ms 141304 KB Output is correct
6 Correct 28 ms 141276 KB Output is correct
7 Correct 28 ms 141348 KB Output is correct
8 Correct 300 ms 332116 KB Output is correct
9 Correct 319 ms 322388 KB Output is correct
10 Correct 146 ms 169296 KB Output is correct
11 Correct 148 ms 168536 KB Output is correct
12 Correct 219 ms 259928 KB Output is correct
13 Correct 244 ms 261800 KB Output is correct
14 Correct 176 ms 163884 KB Output is correct
15 Correct 310 ms 227604 KB Output is correct
16 Correct 276 ms 217428 KB Output is correct
17 Correct 203 ms 213432 KB Output is correct
18 Correct 119 ms 144456 KB Output is correct
19 Correct 92 ms 144048 KB Output is correct
20 Correct 108 ms 144216 KB Output is correct
21 Correct 93 ms 143816 KB Output is correct
22 Correct 93 ms 143700 KB Output is correct
23 Correct 118 ms 144056 KB Output is correct
24 Correct 326 ms 300068 KB Output is correct
25 Correct 385 ms 300392 KB Output is correct
26 Correct 343 ms 298060 KB Output is correct
27 Correct 183 ms 168532 KB Output is correct
28 Correct 401 ms 189488 KB Output is correct
29 Correct 337 ms 156988 KB Output is correct