oj.uz

Submission #947463

# Submission time Handle Problem Language Result Execution time Memory
947463 2024-03-16T08:35:11 Z pcc Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 409 ms 49264 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using namespace __gnu_pbds;

#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>

typedef tree<pair<bs,int>,null_type,less<pair<bs,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int mxn = 1e5+10;


int N,Q;
basic_string<int> arr[mxn];
vector<pair<basic_string<int>,int>> op[mxn];
int ans[mxn];
ordered_set st;
int pppp = 0;

/*
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;
}

*/

void add(bs s){
	st.insert(make_pair(s,++pppp));
}
int getans(bs s){
	auto ss = s;ss.back()++;
	return st.order_of_key(make_pair(ss,-1))-st.order_of_key(make_pair(s,-1));
}

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);
	//rt = newnode();
	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
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 25072 KB Output is correct
2 Correct 118 ms 26268 KB Output is correct
3 Correct 169 ms 41768 KB Output is correct
4 Correct 173 ms 42160 KB Output is correct
5 Correct 59 ms 24660 KB Output is correct
6 Correct 60 ms 24764 KB Output is correct
7 Correct 155 ms 36524 KB Output is correct
8 Correct 155 ms 48536 KB Output is correct
9 Correct 167 ms 49264 KB Output is correct
10 Correct 105 ms 36172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 15232 KB Output is correct
2 Correct 55 ms 12884 KB Output is correct
3 Correct 83 ms 14208 KB Output is correct
4 Correct 58 ms 12176 KB Output is correct
5 Correct 58 ms 13924 KB Output is correct
6 Correct 65 ms 15300 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 6196 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 96 ms 25072 KB Output is correct
9 Correct 118 ms 26268 KB Output is correct
10 Correct 169 ms 41768 KB Output is correct
11 Correct 173 ms 42160 KB Output is correct
12 Correct 59 ms 24660 KB Output is correct
13 Correct 60 ms 24764 KB Output is correct
14 Correct 155 ms 36524 KB Output is correct
15 Correct 155 ms 48536 KB Output is correct
16 Correct 167 ms 49264 KB Output is correct
17 Correct 105 ms 36172 KB Output is correct
18 Correct 71 ms 15232 KB Output is correct
19 Correct 55 ms 12884 KB Output is correct
20 Correct 83 ms 14208 KB Output is correct
21 Correct 58 ms 12176 KB Output is correct
22 Correct 58 ms 13924 KB Output is correct
23 Correct 65 ms 15300 KB Output is correct
24 Correct 147 ms 28828 KB Output is correct
25 Correct 176 ms 31936 KB Output is correct
26 Correct 133 ms 27976 KB Output is correct
27 Correct 235 ms 44824 KB Output is correct
28 Correct 372 ms 46376 KB Output is correct
29 Correct 409 ms 49248 KB Output is correct