Submission #1283241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283241		thuhienne	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	297 ms	343216 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2000009;

#define re exit(0);
#define thuhien "JOI16_RNA"
#define count __count__

int n,m;
string s[100009];

int trie[MAX][27],maxpos[MAX],minpos[MAX],trienode;

void add(string & s,int pos) {
	int currnode = 0;
	for (auto c : s) {
		if (!trie[currnode][c - 'A']) trie[currnode][c - 'A'] = ++trienode;
		currnode = trie[currnode][c - 'A'];
		
		if (maxpos[currnode] == 0) maxpos[currnode] = pos;
		else maxpos[currnode] = max(maxpos[currnode],pos);
		if (minpos[currnode] == 0) minpos[currnode] = pos;
		else minpos[currnode] = min(minpos[currnode],pos);
		
	}
}
pair <int,int> get(string & s) {
	int currnode = 0;
	for (auto c : s) {
		if (!trie[currnode][c - 'A']) return {n + 1,n + 1};
		currnode = trie[currnode][c - 'A'];
	}
	return {minpos[currnode],maxpos[currnode]};
}

int revtrie[MAX][27],revtrienode;
vector <int> count[MAX];
void revadd(string & s,int pos) {
	int currnode = 0;
	for (auto c : s) {
		if (!revtrie[currnode][c - 'A']) revtrie[currnode][c - 'A'] = ++revtrienode;
		currnode = revtrie[currnode][c - 'A'];
		count[currnode].push_back(pos);
	}
}
int revget(string & s,pair <int,int> range) {
	int currnode = 0;
	for (auto c : s) {
		if (!revtrie[currnode][c - 'A']) return 0;
		currnode = revtrie[currnode][c - 'A'];
	}
	return upper_bound(count[currnode].begin(),count[currnode].end(),range.second) - 
		   lower_bound(count[currnode].begin(),count[currnode].end(),range.first);
}


int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
		freopen(thuhien".inp","r",stdin);
		freopen(thuhien".out","w",stdout);
	}
	
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> s[i];
	sort(s + 1,s + 1 + n);

	for (int i = 1;i <= n;i++) {
		add(s[i],i);
		reverse(s[i].begin(),s[i].end());
		revadd(s[i],i);
	}
	
	while (m--) {
		string prefix,suffix;cin >> prefix >> suffix;
		reverse(suffix.begin(),suffix.end());
		cout << revget(suffix,get(prefix)) << '\n';
	}

}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(thuhien".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |                 freopen(thuhien".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40