Submission #112365

#	Time	Username	Problem	Language	Result	Execution time	Memory
112365		ckodser	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	517 ms	47760 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=1e5+500;
const ll inf=1e9+900;

ll A[maxn];
ll ans[maxn];
vector<ll> seg[4*maxn];
ll l[maxn];
ll r[maxn];
ll ls[maxn];
ll rs[maxn];



void bild(ll l,ll r,ll node){
    for(ll i=l;i<r;i++){
	seg[node].pb(A[i]);
    }
    sort(seg[node].begin(),seg[node].end());
    if(l+1==r)return;
    ll mid=(l+r)/2;
    bild(l,mid,2*node);
    bild(mid,r,2*node+1);
}
ll find_ans(ll L,ll R,ll node,ll x){
    if(ls[x]<=L && R<=rs[x]){
	auto it=lower_bound(seg[node].begin(),seg[node].end(),l[x]);
	auto itt=lower_bound(seg[node].begin(),seg[node].end(),r[x]);
	return itt-it;
    }
    if(R<=ls[x] || rs[x]<=L){
	return 0;
    }
    ll mid=(L+R)/2;
    return find_ans(L,mid,2*node,x)+find_ans(mid,R,2*node+1,x);
}

string s[maxn];
pair<string,ll> ru[maxn];
string re[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;
	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;	
    }

    bild(0,n,1);

    
    for(ll i=0;i<q;i++){
	ans[i]=find_ans(0,n,1,i);
    }



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

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