oj.uz

Submission #170813

# Submission time Handle Problem Language Result Execution time Memory
170813 2019-12-26T12:07:14 Z ZwariowanyMarcin Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 496 ms 214644 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

int n, m;	
string s;
vector <string> v;

char S[100005];
int L;

map <char, int> g;

struct trie {
	vector <int> v[2000111];
	int cnt = 1;
	int go[2000111][4];
	
	void add(string &x, int ind) {
		int node = 0;
		for(int i = 0; i < ss(x); ++i) {
			if(go[node][g[x[i]]] == 0)
				go[node][g[x[i]]] = cnt++;
			node = go[node][g[x[i]]];
			v[node].pb(ind);
		}
	}
	
	pair<int,int> q1(string &x) {
		int node = 0;
		for(int i = 0; i < ss(x); ++i) {
			node = go[node][g[x[i]]];
			if(!node) return {-1, -1};
		}
		return {v[node][0], v[node].back()};
	} 
	
	int q2(int L, int R, string &x) {
		int node = 0;
		for(int i = 0; i < ss(x); ++i) {
			node = go[node][g[x[i]]];
			if(!node) return 0;
		}
		return (int) (upper_bound(v[node].begin(), v[node].end(), R) - lower_bound(v[node].begin(), v[node].end(), L));
	}		
} ja, on;

int main() {
	g['A'] = 0;
	g['C'] = 1;
	g['G'] = 2;
	g['U'] = 3;
	scanf("%d %d", &n, &m);
	FOR(i, n) {
		scanf("%s", S);
		L = strlen(S);
		s = "";
		for(int j = 0; j < L; ++j)
			s.pb(S[j]);
		v.pb(s);
	}
	sort(v.begin(), v.end());
	FOR(i, n) {
		s = v[i];
		ja.add(s, i);
		reverse(s.begin(), s.end());
		on.add(s, i);
	}
	FOR(i, m) {
		scanf("%s", S);
		L = strlen(S);
		s = "";
		for(int j = 0; j < L; ++j)
			s.pb(S[j]);
		pair<int, int> w = ja.q1(s);
		scanf("%s", S);
		L = strlen(S);
		s = "";
		for(int j = 0; j < L; ++j)
			s.pb(S[j]);
		if(w == mp(-1, -1)) {
			printf("0\n");
			continue;
		}
		reverse(s.begin(), s.end());
		printf("%d\n", on.q2(w.fi, w.se, s));
	}
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
   ~~~~~^~~~~~~~~
selling_rna.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
   ~~~~~^~~~~~~~~
selling_rna.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
   ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94476 KB Output is correct
2 Correct 90 ms 94332 KB Output is correct
3 Correct 89 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 91 ms 94328 KB Output is correct
6 Correct 95 ms 94356 KB Output is correct
7 Correct 105 ms 94300 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 204152 KB Output is correct
2 Correct 485 ms 198644 KB Output is correct
3 Correct 477 ms 202444 KB Output is correct
4 Correct 468 ms 197748 KB Output is correct
5 Correct 444 ms 212960 KB Output is correct
6 Correct 455 ms 214644 KB Output is correct
7 Correct 255 ms 118136 KB Output is correct
8 Correct 477 ms 181528 KB Output is correct
9 Correct 425 ms 169460 KB Output is correct
10 Correct 374 ms 165876 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 97892 KB Output is correct
2 Correct 126 ms 96948 KB Output is correct
3 Correct 127 ms 97252 KB Output is correct
4 Correct 119 ms 96996 KB Output is correct
5 Correct 128 ms 96876 KB Output is correct
6 Correct 131 ms 97256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94476 KB Output is correct
2 Correct 90 ms 94332 KB Output is correct
3 Correct 89 ms 94328 KB Output is correct
4 Correct 89 ms 94328 KB Output is correct
5 Correct 91 ms 94328 KB Output is correct
6 Correct 95 ms 94356 KB Output is correct
7 Correct 105 ms 94300 KB Output is correct
8 Correct 496 ms 204152 KB Output is correct
9 Correct 485 ms 198644 KB Output is correct
10 Correct 477 ms 202444 KB Output is correct
11 Correct 468 ms 197748 KB Output is correct
12 Correct 444 ms 212960 KB Output is correct
13 Correct 455 ms 214644 KB Output is correct
14 Correct 255 ms 118136 KB Output is correct
15 Correct 477 ms 181528 KB Output is correct
16 Correct 425 ms 169460 KB Output is correct
17 Correct 374 ms 165876 KB Output is correct
18 Correct 128 ms 97892 KB Output is correct
19 Correct 126 ms 96948 KB Output is correct
20 Correct 127 ms 97252 KB Output is correct
21 Correct 119 ms 96996 KB Output is correct
22 Correct 128 ms 96876 KB Output is correct
23 Correct 131 ms 97256 KB Output is correct
24 Correct 474 ms 186540 KB Output is correct
25 Correct 491 ms 186804 KB Output is correct
26 Correct 489 ms 185712 KB Output is correct
27 Correct 440 ms 185328 KB Output is correct
28 Correct 412 ms 131960 KB Output is correct
29 Correct 246 ms 110812 KB Output is correct