Submission #403565

#	Time	Username	Problem	Language	Result	Execution time	Memory
403565		FEDIKUS	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	667 ms	219204 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];
str nizrr[maxn];
pair<str,int> nizr[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,str *niz){
    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,str *niz){
    int l=0;
    int r=n-1;
    int prvi=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int odg=sta(mid,p,niz);
        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,niz);
        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 {prvi,drugi};
}

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 vl,int vr){
    if(tl<=l && r<=tr){
        return upper_bound(tree[ind].begin(),tree[ind].end(),vr)-lower_bound(tree[ind].begin(),tree[ind].end(),vl);
    }
    int mid=l+(r-l)/2;
    int ret=0;
    if(tl<=mid) ret+=query(2*ind,l,mid,tl,tr,vl,vr);
    if(tr>mid) ret+=query(2*ind+1,mid+1,r,tl,tr,vl,vr);
    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++){
        reverse(niz[i].begin(),niz[i].end());
        nizr[i].xx=niz[i];
        nizr[i].yy=i;
        nizrr[i]=niz[i];
        reverse(niz[i].begin(),niz[i].end());
    }
    sort(nizr,nizr+n);
    sort(nizrr,nizrr+n);
    for(int i=0;i<n;i++){
        novi[nizr[i].yy]=i;
    }
    koliko=n;
    build(1,0,koliko-1);
    while(m--){
        str p,q;
        cin>>p>>q;
        pii pom=range(p,n,niz);
        reverse(q.begin(),q.end());
        pii pom2=range(q,n,nizrr);
        if(pom.xx==-1 || pom.yy==-1){cout<<0<<"\n"; continue;}
        /*int res=0;
        for(int i=pom.xx;i<=pom.yy;i++){
            if(novi[i]>=pom2.xx && novi[i]<=pom2.yy)  res++;
        }*/
        //cout<<pom.xx<<" "<<pom.yy<<"\n";
        //cout<<pom2.xx<<" "<<pom2.yy<<"\n";
        cout<<query(1,0,koliko-1,pom.xx,pom.yy,pom2.xx,pom2.yy)<<"\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&, str*)':
selling_rna.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   53 |     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:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(i<a.size() || j<b.size()){
      |           ~^~~~~~~~~
selling_rna.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     while(i<a.size() || j<b.size()){
      |                         ~^~~~~~~~~
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()) res[tren]=min(res[tren],a[i]);
      |            ~^~~~~~~~~
selling_rna.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if(j<b.size()) res[tren]=min(res[tren],b[j]);
      |            ~^~~~~~~~~
selling_rna.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(i<a.size() && a[i]==res[tren]) i++;
      |            ~^~~~~~~~~
selling_rna.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         else if(j<b.size() && b[j]==res[tren]) j++;
      |                 ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40