oj.uz

Submission #933043

# Submission time Handle Problem Language Result Execution time Memory
933043 2024-02-24T23:05:13 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 88 ms 127300 KB 
//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=500005; 

ll n, m, k, xd, zd;
ll a[N], b[N], tp[4][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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29272 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 127300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 30664 KB Output is correct
2 Correct 21 ms 31120 KB Output is correct
3 Correct 24 ms 31068 KB Output is correct
4 Correct 20 ms 30880 KB Output is correct
5 Correct 22 ms 31036 KB Output is correct
6 Correct 26 ms 31012 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29272 KB Output is correct
8 Runtime error 88 ms 127300 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -