Submission #253322

#	Time	Username	Problem	Language	Result	Execution time	Memory
253322		Lawliet	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	665 ms	227584 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int MAXL = 5;
const int MAXN = 100010;
const int MAXS = 2000010;

char bases[] = "AGCU";

class Trie
{
	public:

		int conv(char c)
		{
			for(int i = 0 ; i < 4 ; i++)
				if( bases[i] == c ) return i;
		}

		void addString(string& s, int ind)
		{
			int cur = 0;

			for(int i = 0 ; i < (int)s.size() ; i++)
			{
				int c = conv( s[i] );

				if( tree[cur][c] == 0 )
					tree[cur][c] = ++cnt;

				cur = tree[cur][c];
				allInd[cur].push_back( ind );
			}
		}

		void getInterval(string& s, int& L, int& R)
		{
			L = R = 0;
			int cur = 0;

			for(int i = 0 ; i < (int)s.size() ; i++)
			{
				int c = conv( s[i] );

				if( tree[cur][c] == 0 )
					return;

				cur = tree[cur][c];
			}

			L = allInd[cur].front();
			R = allInd[cur].back();
		}

		int getQtdInterval(string& s, int L, int R)
		{
			int cur = 0;

			for(int i = 0 ; i < (int)s.size() ; i++)
			{
				int c = conv( s[i] );

				if( tree[cur][c] == 0 )
					return 0;

				cur = tree[cur][c];
			}

			auto itR = upper_bound( allInd[cur].begin() , allInd[cur].end() , R );
			auto itL = lower_bound( allInd[cur].begin() , allInd[cur].end() , L );

			return itR - itL;
		}

		Trie() : cnt(1) {}

	protected:

		int cnt;

		int tree[MAXS][MAXL];
		vector<int> allInd[MAXS];
};

int n, q;

string s[MAXN];

Trie prefixTrie, suffixTrie;

int main()
{
	cin >> n >> q;

	for(int i = 1 ; i <= n ; i++)
		cin >> s[i];

	sort( s + 1 , s + n + 1 );

	for(int i = 1 ; i <= n ; i++)
	{
		prefixTrie.addString( s[i] , i );

		reverse( s[i].begin() , s[i].end() );
		suffixTrie.addString( s[i] , i );
	}

	for(int i = 1 ; i <= q ; i++)
	{
		string prefix, suffix;
		cin >> prefix >> suffix;

		reverse( suffix.begin() , suffix.end() );

		int L, R;
		prefixTrie.getInterval( prefix , L , R );

		printf("%d\n",suffixTrie.getQtdInterval( suffix , L , R ));
	}
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int Trie::conv(char)':
selling_rna.cpp:19:3: warning: control reaches end of non-void function [-Wreturn-type]
   }
   ^

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