oj.uz

Submission #403505

# Submission time Handle Problem Language Result Execution time Memory
403505 2021-05-13T08:53:51 Z FEDIKUS Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 473768 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=1e5+10;
const int maxa=2e6+10;
const int pp=31;
const int mod=1e9+7;
str niz[maxn];
int novi[maxa];
pii kad[maxn];
int koliko=0;
int koji[256];
vector<int> tree[4*maxa+50];

int mul(ll a,ll b){
    if(a*b>=mod) return a*b%mod;
    return a*b;
}

int add(ll a,ll b){
    if(a+b>=mod) return (a+b)%mod;
    return a+b;
}

int sta(int mid,str &p){
    if(p.size()>niz[mid].size()){
        return (p<niz[mid] ? 3:1);
    }
    for(int i=0;i<min(p.size(),niz[mid].size());i++){
        if(p[i]<niz[mid][i]) return 3;
        if(p[i]>niz[mid][i]) return 1;
    }
    return 2;
}

pii range(str &p,int n){
    int l=0;
    int r=n-1;
    int prvi=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int odg=sta(mid,p);
        if(odg==1){
            l=mid+1;
        }else if(odg==2){
            r=mid-1;
            prvi=mid;
        }else r=mid-1;
    }

    l=0;
    r=n-1;
    int drugi=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int odg=sta(mid,p);
        if(odg==1){
            l=mid+1;
        }else if(odg==2){
            l=mid+1;
            drugi=mid;
        }else r=mid-1;
    }
    if(prvi==-1 || drugi==-1) return {-1,-1};
    return {kad[prvi].xx,kad[drugi].yy};
}

void spoji(vector<int> &a,vector<int> &b,vector<int> &res){
    res.resize(a.size()+b.size());
    int tren=0;
    int i=0;
    int j=0;
    while(i<a.size() || j<b.size()){
        res[tren]=INT_MAX;
        if(i<a.size()) res[tren]=min(res[tren],a[i]);
        if(j<b.size()) res[tren]=min(res[tren],b[j]);
        if(i<a.size() && a[i]==res[tren]) i++;
        else if(j<b.size() && b[j]==res[tren]) j++;
        tren++;
    }
}

void build(int ind,int l,int r){
    if(l==r){
        tree[ind]={novi[l]};
        return;
    }
    int mid=l+(r-l)/2;
    build(2*ind,l,mid);
    build(2*ind+1,mid+1,r);
    spoji(tree[2*ind],tree[2*ind+1],tree[ind]);
}

int query(int ind,int l,int r,int tl,int tr,int v){
    if(l==r){
        return int(novi[l]==v);
    }
    if(tl<=l && r<=tr){
        return upper_bound(tree[ind].begin(),tree[ind].end(),v)-lower_bound(tree[ind].begin(),tree[ind].end(),v);
    }
    int mid=l+(r-l)/2;
    int ret=0;
    if(tl<=mid) ret+=query(2*ind,l,mid,tl,tr,v);
    if(tr>mid) ret+=query(2*ind+1,mid+1,r,tl,tr,v);
    return ret;
}

void solve(){
    koji['A']=1;
    koji['G']=2;
    koji['C']=3;
    koji['U']=4;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>niz[i];
    sort(niz,niz+n);
    for(int i=0;i<n;i++){
        int hsh=0;
        kad[i].xx=koliko;
        for(int j=niz[i].size()-1;j>=0;j--){
            hsh=mul(hsh,pp);
            hsh=add(hsh,mul(pp,koji[niz[i][j]]));
            novi[koliko++]=hsh;
        }
        kad[i].yy=koliko-1;
    }
    build(1,0,koliko-1);
    while(m--){
        str p,q;
        cin>>p>>q;
        pii pom=range(p,n);
        if(pom.xx==-1 || pom.yy==-1){cout<<0<<"\n"; continue;}
        int hsh=0;
        for(int j=q.size()-1;j>=0;j--){
            hsh=mul(hsh,pp);
            hsh=add(hsh,mul(pp,koji[q[j]]));
        }
        cout<<query(1,0,koliko-1,pom.xx,pom.yy,hsh)<<"\n";
    }
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int sta(int, str&)':
selling_rna.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   51 |     for(int i=0;i<min(p.size(),niz[mid].size());i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void spoji(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
selling_rna.cpp:95:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     while(i<a.size() || j<b.size()){
      |           ~^~~~~~~~~
selling_rna.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     while(i<a.size() || j<b.size()){
      |                         ~^~~~~~~~~
selling_rna.cpp:97:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         if(i<a.size()) res[tren]=min(res[tren],a[i]);
      |            ~^~~~~~~~~
selling_rna.cpp:98:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         if(j<b.size()) res[tren]=min(res[tren],b[j]);
      |            ~^~~~~~~~~
selling_rna.cpp:99:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if(i<a.size() && a[i]==res[tren]) i++;
      |            ~^~~~~~~~~
selling_rna.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         else if(j<b.size() && b[j]==res[tren]) j++;
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:144:46: warning: array subscript has type 'char' [-Wchar-subscripts]
  144 |             hsh=add(hsh,mul(pp,koji[niz[i][j]]));
      |                                              ^
selling_rna.cpp:158:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |             hsh=add(hsh,mul(pp,koji[q[j]]));
      |                                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 191300 KB Output is correct
2 Correct 103 ms 191284 KB Output is correct
3 Correct 102 ms 191340 KB Output is correct
4 Correct 104 ms 191340 KB Output is correct
5 Correct 107 ms 191444 KB Output is correct
6 Correct 102 ms 191248 KB Output is correct
7 Correct 102 ms 191264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1154 ms 471684 KB Output is correct
2 Correct 1155 ms 471632 KB Output is correct
3 Correct 1036 ms 471708 KB Output is correct
4 Correct 1028 ms 471620 KB Output is correct
5 Correct 757 ms 360588 KB Output is correct
6 Correct 777 ms 363176 KB Output is correct
7 Correct 849 ms 400028 KB Output is correct
8 Correct 1112 ms 473412 KB Output is correct
9 Correct 1106 ms 472688 KB Output is correct
10 Correct 1067 ms 471064 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 204336 KB Output is correct
2 Correct 216 ms 203824 KB Output is correct
3 Correct 216 ms 203972 KB Output is correct
4 Correct 199 ms 203996 KB Output is correct
5 Correct 202 ms 203840 KB Output is correct
6 Correct 217 ms 204092 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 191300 KB Output is correct
2 Correct 103 ms 191284 KB Output is correct
3 Correct 102 ms 191340 KB Output is correct
4 Correct 104 ms 191340 KB Output is correct
5 Correct 107 ms 191444 KB Output is correct
6 Correct 102 ms 191248 KB Output is correct
7 Correct 102 ms 191264 KB Output is correct
8 Correct 1154 ms 471684 KB Output is correct
9 Correct 1155 ms 471632 KB Output is correct
10 Correct 1036 ms 471708 KB Output is correct
11 Correct 1028 ms 471620 KB Output is correct
12 Correct 757 ms 360588 KB Output is correct
13 Correct 777 ms 363176 KB Output is correct
14 Correct 849 ms 400028 KB Output is correct
15 Correct 1112 ms 473412 KB Output is correct
16 Correct 1106 ms 472688 KB Output is correct
17 Correct 1067 ms 471064 KB Output is correct
18 Correct 198 ms 204336 KB Output is correct
19 Correct 216 ms 203824 KB Output is correct
20 Correct 216 ms 203972 KB Output is correct
21 Correct 199 ms 203996 KB Output is correct
22 Correct 202 ms 203840 KB Output is correct
23 Correct 217 ms 204092 KB Output is correct
24 Correct 1258 ms 471800 KB Output is correct
25 Correct 1389 ms 472036 KB Output is correct
26 Correct 1181 ms 471692 KB Output is correct
27 Correct 1110 ms 471796 KB Output is correct
28 Execution timed out 1612 ms 473768 KB Time limit exceeded
29 Halted 0 ms 0 KB -