Submission #112363

#	Time	Username	Problem	Language	Result	Execution time	Memory
112363		ckodser	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1563 ms	114296 KiB

selling_rna

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e6+500;
const ll inf=1e9+900;

string s[maxn];
pair<string,ll> ru[maxn];
string re[maxn];

ll A[maxn];
ll l[maxn];
ll r[maxn];
ll ls[maxn];
ll rs[maxn];
ll ans[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,q;
    cin>>n>>q;
    for(ll i=0;i<n;i++){
	cin>>s[i];
    }
    sort(s,s+n);
    for(ll i=0;i<n;i++){
	ru[i]=mp(s[i],i);
	reverse(ru[i].F.begin(),ru[i].F.end());
    }
    sort(ru,ru+n);
    for(ll i=0;i<n;i++){
	re[i]=ru[i].F;
	A[i]=ru[i].S;
    }
    for(ll i=0;i<q;i++){
	string a,b;
	cin>>a>>b;
	l[i]=lower_bound(s,s+n,a)-s;
	a.back()++;
	r[i]=lower_bound(s,s+n,a)-s;
//	cout<<l[i]<<' '<<r[i]<<endl;
	reverse(b.begin(),b.end());
	ls[i]=lower_bound(re,re+n,b)-re;
	b.back()++;
	rs[i]=lower_bound(re,re+n,b)-re;	
    }
    for(ll i=0;i<q;i++){
	for(ll j=ls[i];j<rs[i];j++){
	    if(l[i]<=A[j] && A[j]<r[i]){
		ans[i]++;
	    }
	}
    }

    


    for(ll i=0;i<q;i++){
	cout<<ans[i]<<endl;
    }
}

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