oj.uz

Submission #552149

# Submission time Handle Problem Language Result Execution time Memory
552149 2022-04-22T13:58:15 Z nishkarsh Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 446 ms 223516 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 1e6+1;
const int mod = 1e9+7;
const int letters = 4;
string inp[upperlimit];
int toint(char c){
	if(c=='A') return 0;
	if(c=='U') return 1;
	if(c=='G') return 2;
	return 3;
}
struct trie_node
{
	vi indices;
	int child[letters];
	trie_node(){
		for(int i = 0; i < letters; i++) child[i]=0;
	}
};
trie_node default_trienode;
class trie {
	vector<trie_node> tree;
	int cur_node,sz=1;
public:
	trie() {
		tree.resize(1);
	}
	void addstring(string s,int ind){
		cur_node=0;
		for(auto i : s){
			tree[cur_node].indices.pb(ind);
			if(! tree[cur_node].child[toint(i)]){
				tree[cur_node].child[toint(i)]=sz++;
				tree.pb(default_trienode);
			}
			cur_node = tree[cur_node].child[toint(i)];
		}
		tree[cur_node].indices.pb(ind);
	}
	pii query_range(string s){
		cur_node = 0;
		for(auto i : s){
			if(! tree[cur_node].child[toint(i)]) return(mp(0,0));
			cur_node = tree[cur_node].child[toint(i)];
		}
		return mp(tree[cur_node].indices.front(),tree[cur_node].indices.back());
	}
	int query(string s,int l,int r){
		cur_node = 0;
		for(auto i : s){
			if(! tree[cur_node].child[toint(i)]) return 0;
			cur_node = tree[cur_node].child[toint(i)];
		}
		return int(upper_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),r) - lower_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),l));
	}
};
int main(){
	int n,m;
	string pref,suff;
	trie str,revstr;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> inp[i];
	sort(inp+1,inp+n+1);
	for(int i = 1; i <= n; i++){
		str.addstring(inp[i],i);
		reverse(inp[i].begin(),inp[i].end());
		revstr.addstring(inp[i],i);
	}
	while(m--){
		cin >> pref >> suff;
		pii range = str.query_range(pref);
		reverse(suff.begin(),suff.end());
		cout << revstr.query(suff,range.F,range.S) << "\n";
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 16 ms 31584 KB Output is correct
3 Correct 19 ms 31608 KB Output is correct
4 Correct 15 ms 31640 KB Output is correct
5 Correct 16 ms 31608 KB Output is correct
6 Correct 15 ms 31620 KB Output is correct
7 Correct 15 ms 31572 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 186492 KB Output is correct
2 Correct 362 ms 177448 KB Output is correct
3 Correct 361 ms 183428 KB Output is correct
4 Correct 389 ms 176192 KB Output is correct
5 Correct 387 ms 223516 KB Output is correct
6 Correct 404 ms 223512 KB Output is correct
7 Correct 197 ms 51824 KB Output is correct
8 Correct 391 ms 158468 KB Output is correct
9 Correct 374 ms 145276 KB Output is correct
10 Correct 284 ms 141320 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 33748 KB Output is correct
2 Correct 88 ms 33704 KB Output is correct
3 Correct 100 ms 33736 KB Output is correct
4 Correct 87 ms 33620 KB Output is correct
5 Correct 84 ms 33612 KB Output is correct
6 Correct 108 ms 33724 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 16 ms 31584 KB Output is correct
3 Correct 19 ms 31608 KB Output is correct
4 Correct 15 ms 31640 KB Output is correct
5 Correct 16 ms 31608 KB Output is correct
6 Correct 15 ms 31620 KB Output is correct
7 Correct 15 ms 31572 KB Output is correct
8 Correct 377 ms 186492 KB Output is correct
9 Correct 362 ms 177448 KB Output is correct
10 Correct 361 ms 183428 KB Output is correct
11 Correct 389 ms 176192 KB Output is correct
12 Correct 387 ms 223516 KB Output is correct
13 Correct 404 ms 223512 KB Output is correct
14 Correct 197 ms 51824 KB Output is correct
15 Correct 391 ms 158468 KB Output is correct
16 Correct 374 ms 145276 KB Output is correct
17 Correct 284 ms 141320 KB Output is correct
18 Correct 143 ms 33748 KB Output is correct
19 Correct 88 ms 33704 KB Output is correct
20 Correct 100 ms 33736 KB Output is correct
21 Correct 87 ms 33620 KB Output is correct
22 Correct 84 ms 33612 KB Output is correct
23 Correct 108 ms 33724 KB Output is correct
24 Correct 390 ms 162280 KB Output is correct
25 Correct 446 ms 162644 KB Output is correct
26 Correct 358 ms 160968 KB Output is correct
27 Correct 373 ms 160480 KB Output is correct
28 Correct 410 ms 72392 KB Output is correct
29 Correct 316 ms 45444 KB Output is correct