oj.uz

Submission #947451

# Submission time Handle Problem Language Result Execution time Memory
947451 2024-03-16T08:15:27 Z pcc Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 118 ms 56732 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define bs basic_string<int>

const int mxn = 1e5+10;


int N,Q;
basic_string<int> arr[mxn];
vector<pair<basic_string<int>,int>> op[mxn];
int ans[mxn];

struct node{
	int ch[4];
	int dp;
};

int ppp = 0;
int newnode(){
	return ++ppp;
}

node trie[mxn*100];
int rt;

void add(bs s){
	int now = rt;
	for(auto &i:s){
		if(!trie[now].ch[i])trie[now].ch[i] = newnode();
		now = trie[now].ch[i];
		trie[now].dp++;
	}
	return;
}
int getans(basic_string<int> s){
	int now = rt;
	for(auto &i:s){
		now = trie[now].ch[i];
	}
	return trie[now].dp;
}

basic_string<int> conv(string s){
	basic_string<int> re;
	for(auto &i:s){
		if(i == 'A')re += 0;
		else if(i == 'C')re += 1;
		else if(i == 'G')re += 2;
		else re += 3;
	}
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		string s;
		cin>>s;
		arr[i] = conv(s);
	}
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=Q;i++){
		string sa,sb;
		cin>>sa>>sb;
		auto ta = conv(sa),tb = conv(sb);
		reverse(tb.begin(),tb.end());
		auto lit = lower_bound(arr+1,arr+N+1,ta)-arr;
		ta.back()++;
		auto rit = lower_bound(arr+1,arr+N+1,ta)-arr;
		op[lit].push_back(make_pair(tb,i));
		op[rit].push_back(make_pair(tb,-i));
	}
	for(int i = N;i>=1;i--){
		reverse(arr[i].begin(),arr[i].end());
		add(arr[i]);
		for(auto &j:op[i]){
			if(j.sc>0){
				ans[j.sc] += getans(j.fs);
			}
			else ans[-j.sc] -= getans(j.fs);
		}
	}
	for(int i = 1;i<=Q;i++)cout<<ans[i]<<'\n';
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 56732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 11888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -