oj.uz

Submission #585999

# Submission time Handle Problem Language Result Execution time Memory
585999 2022-06-29T17:00:52 Z Ace Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1101 ms 249080 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> pii;
typedef pair<string,int> psi;
const int N = 1e5;
const int MAXN = 2e6;

struct trie{
	int nxt[4];
	vector<int> isi;
};

trie dep[MAXN+5], bel[MAXN+5];
int cntDep = 0;
int cntBel = 0;

int getNum(char x){
	if(x == 'A') return 0;
	if(x == 'G') return 1;
	if(x == 'C') return 2;
	return 3;
}

void insert(int node, string &s, int idx, int id, trie *t, int &cnt){
	t[node].isi.push_back(idx);
	if(id == s.size()) return;
	int cur = getNum(s[id]);
	if(t[node].nxt[cur] == -1) {
		cnt++;
		memset(t[cnt].nxt,-1,sizeof(t[cnt].nxt));
		t[node].nxt[cur] = cnt;
	}
	insert(t[node].nxt[cur], s, idx, id+1, t, cnt);
}

vector<int> query(int node, string &s, int id, trie *t){
	if(node == -1) return vector<int>();
	if(id == s.size()) {
		return t[node].isi;
	}
	int cur = getNum(s[id]);
	return query(t[node].nxt[cur], s, id+1, t);
}

string li[N+5];
 
int n,m;
 
string pre[N+5], suf[N+5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> li[i];
	}
	
	sort(li+1,li+n+1);
	memset(dep[0].nxt,-1,sizeof(dep[0].nxt));
	memset(bel[0].nxt,-1,sizeof(bel[0].nxt));
	
	for(int i=1;i<=n;i++){
		insert(0, li[i], i, 0, dep, cntDep);
		string rev = li[i];
		reverse(rev.begin(), rev.end());
		insert(0, rev, i, 0, bel, cntBel);
	}
	
	
	for(int i=1;i<=m;i++){
		cin >> pre[i] >> suf[i];
		reverse(suf[i].begin(), suf[i].end());
		vector<int> retPre = query(0, pre[i], 0, dep);
		if(retPre.size() == 0) {
			cout << "0\n";
			continue;
		}
		vector<int> retSuf = query(0, suf[i], 0, bel);
		int l = retPre[0];
		int r = retPre.back();
		int idl = lower_bound(retSuf.begin(), retSuf.end(), l) - retSuf.begin();
		int idr = upper_bound(retSuf.begin(), retSuf.end(), r) - retSuf.begin();
		cout << idr-idl << "\n";
	}
	
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void insert(int, std::string&, int, int, trie*, int&)':
selling_rna.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if(id == s.size()) return;
      |     ~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::vector<int> query(int, std::string&, int, trie*)':
selling_rna.cpp:39:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  if(id == s.size()) {
      |     ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 166220 KB Output is correct
2 Correct 72 ms 166248 KB Output is correct
3 Correct 69 ms 166228 KB Output is correct
4 Correct 75 ms 166260 KB Output is correct
5 Correct 72 ms 166184 KB Output is correct
6 Correct 70 ms 166200 KB Output is correct
7 Correct 70 ms 166168 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 245192 KB Output is correct
2 Correct 268 ms 240876 KB Output is correct
3 Correct 234 ms 243364 KB Output is correct
4 Correct 237 ms 240180 KB Output is correct
5 Correct 267 ms 246364 KB Output is correct
6 Correct 255 ms 249080 KB Output is correct
7 Correct 141 ms 194252 KB Output is correct
8 Correct 274 ms 235208 KB Output is correct
9 Correct 250 ms 226892 KB Output is correct
10 Correct 212 ms 221216 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 168628 KB Output is correct
2 Correct 146 ms 168140 KB Output is correct
3 Correct 196 ms 168248 KB Output is correct
4 Correct 143 ms 168276 KB Output is correct
5 Correct 167 ms 168136 KB Output is correct
6 Correct 171 ms 168256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 166220 KB Output is correct
2 Correct 72 ms 166248 KB Output is correct
3 Correct 69 ms 166228 KB Output is correct
4 Correct 75 ms 166260 KB Output is correct
5 Correct 72 ms 166184 KB Output is correct
6 Correct 70 ms 166200 KB Output is correct
7 Correct 70 ms 166168 KB Output is correct
8 Correct 264 ms 245192 KB Output is correct
9 Correct 268 ms 240876 KB Output is correct
10 Correct 234 ms 243364 KB Output is correct
11 Correct 237 ms 240180 KB Output is correct
12 Correct 267 ms 246364 KB Output is correct
13 Correct 255 ms 249080 KB Output is correct
14 Correct 141 ms 194252 KB Output is correct
15 Correct 274 ms 235208 KB Output is correct
16 Correct 250 ms 226892 KB Output is correct
17 Correct 212 ms 221216 KB Output is correct
18 Correct 382 ms 168628 KB Output is correct
19 Correct 146 ms 168140 KB Output is correct
20 Correct 196 ms 168248 KB Output is correct
21 Correct 143 ms 168276 KB Output is correct
22 Correct 167 ms 168136 KB Output is correct
23 Correct 171 ms 168256 KB Output is correct
24 Correct 286 ms 235188 KB Output is correct
25 Correct 336 ms 235904 KB Output is correct
26 Correct 263 ms 234388 KB Output is correct
27 Correct 298 ms 234632 KB Output is correct
28 Correct 1101 ms 200976 KB Output is correct
29 Correct 228 ms 180336 KB Output is correct