Submission #403505

#	Time	Username	Problem	Language	Result	Execution time	Memory
403505		FEDIKUS	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1612 ms	473768 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40