Submission #933044

#	Time	Username	Problem	Language	Result	Execution time	Memory
933044		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	199 ms	246864 KiB

selling_rna

//holasoydember:D
//20/01/2024
#include <bits/stdc++.h>

#define pb push_back
#define all(n) n.begin(),n.end()
#define Z size()
#define S second
#define F first 
#define ll long long
#define fo(x, y, z) for(ll x=y; x<=z; x++)
#define of(x, y, z) for(ll x=y; x>=z; x--)

using namespace std;

void value(int in){cout<<((in)?"YES\n":"NO\n");return;}

const ll md=1e9+7, mod=998244353, N=2000005; 

ll n, m, k, xd, zd;
ll a[N], b[N], tp[2][4][N], d[10];
string ss[N];
//set<ll> f, g;
vector<ll> v[N];
//queue<pair<ll,ll>> q;

ll ch(char c) {
    if (c=='A') return 0;
    if (c=='C') return 1;
    if (c=='G') return 2;
    return 3;
}
void add(string s, ll j, ll h, ll f){
	k=1;
	fo(i,0,s.Z-1){
        ll c;
        if(f==1)c=ch(s[s.Z-i-1]);
        else c=ch(s[i]);
		if(tp[h][c][k]==0)tp[h][c][k]=d[h]++;
		k=tp[h][c][k];
		if(h==0){
			if(a[k]==0)a[k]=j;
			b[k]=max(b[k],j);
		}
		else v[k].push_back(j);
	}
	return;
}
ll get(string s, ll h, ll f) {
	k=1;
	fo(i,0,s.Z-1){
	    ll c;
        if (f==1)c=ch(s[s.Z-i-1]);
        else c=ch(s[i]);
		k=tp[h][c][k];
		if (k==0)return 0;
	}
	return k;
}

void CD(){
    cin>>n>>m;
	d[0]=d[1]=2;
	fo(i,0,n-1)cin>>ss[i];
    
    sort(ss, ss+n);
    
	fo(x,0,n-1) {
		add(ss[x],x+1,0,0);
		add(ss[x],x+1,1,1);
	}
	fo(x,0,m-1){
		string s, t;
		cin>>s>>t;
		ll h=get(s, 0, 0), k=get(t, 1, 1);
		ll g=lower_bound(v[k].begin(), v[k].end(), a[h])-v[k].begin(), l=upper_bound(v[k].begin(), v[k].end(), b[h])-v[k].begin();
		cout<<max(0ll, l-g)<<"\n";
	}
    
    return;
}

int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    
    int t=1;
    //cin>>t;
    
    while(t--){
        CD();
    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::string, long long int, long long int, long long int)':
selling_rna.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define fo(x, y, z) for(ll x=y; x<=z; x++)
......
   35 |  fo(i,0,s.Z-1){
      |     ~~~~~~~~~                     
selling_rna.cpp:35:2: note: in expansion of macro 'fo'
   35 |  fo(i,0,s.Z-1){
      |  ^~
selling_rna.cpp: In function 'long long int get(std::string, long long int, long long int)':
selling_rna.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define fo(x, y, z) for(ll x=y; x<=z; x++)
......
   51 |  fo(i,0,s.Z-1){
      |     ~~~~~~~~~                     
selling_rna.cpp:51:2: note: in expansion of macro 'fo'
   51 |  fo(i,0,s.Z-1){
      |  ^~

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