oj.uz

Submission #933044

# Submission time Handle Problem Language Result Execution time Memory
933044 2024-02-24T23:06:17 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 199 ms 246864 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=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

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 31 ms 111440 KB Output is correct
2 Correct 31 ms 111448 KB Output is correct
3 Correct 28 ms 111448 KB Output is correct
4 Correct 30 ms 111452 KB Output is correct
5 Correct 27 ms 111452 KB Output is correct
6 Correct 26 ms 111316 KB Output is correct
7 Correct 27 ms 111356 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 237396 KB Output is correct
2 Correct 170 ms 230648 KB Output is correct
3 Correct 108 ms 224328 KB Output is correct
4 Correct 109 ms 219852 KB Output is correct
5 Correct 175 ms 244988 KB Output is correct
6 Correct 151 ms 246864 KB Output is correct
7 Correct 67 ms 128848 KB Output is correct
8 Correct 140 ms 176468 KB Output is correct
9 Correct 137 ms 175712 KB Output is correct
10 Correct 109 ms 175620 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 112716 KB Output is correct
2 Correct 47 ms 112732 KB Output is correct
3 Correct 45 ms 112732 KB Output is correct
4 Correct 42 ms 112592 KB Output is correct
5 Correct 42 ms 112844 KB Output is correct
6 Correct 47 ms 112724 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 111440 KB Output is correct
2 Correct 31 ms 111448 KB Output is correct
3 Correct 28 ms 111448 KB Output is correct
4 Correct 30 ms 111452 KB Output is correct
5 Correct 27 ms 111452 KB Output is correct
6 Correct 26 ms 111316 KB Output is correct
7 Correct 27 ms 111356 KB Output is correct
8 Correct 183 ms 237396 KB Output is correct
9 Correct 170 ms 230648 KB Output is correct
10 Correct 108 ms 224328 KB Output is correct
11 Correct 109 ms 219852 KB Output is correct
12 Correct 175 ms 244988 KB Output is correct
13 Correct 151 ms 246864 KB Output is correct
14 Correct 67 ms 128848 KB Output is correct
15 Correct 140 ms 176468 KB Output is correct
16 Correct 137 ms 175712 KB Output is correct
17 Correct 109 ms 175620 KB Output is correct
18 Correct 45 ms 112716 KB Output is correct
19 Correct 47 ms 112732 KB Output is correct
20 Correct 45 ms 112732 KB Output is correct
21 Correct 42 ms 112592 KB Output is correct
22 Correct 42 ms 112844 KB Output is correct
23 Correct 47 ms 112724 KB Output is correct
24 Correct 178 ms 219988 KB Output is correct
25 Correct 199 ms 220132 KB Output is correct
26 Correct 192 ms 218812 KB Output is correct
27 Correct 108 ms 210516 KB Output is correct
28 Correct 164 ms 150252 KB Output is correct
29 Correct 92 ms 124476 KB Output is correct