Submission #170813

#	Time	Username	Problem	Language	Result	Execution time	Memory
170813		ZwariowanyMarcin	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	496 ms	214644 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40