Submission #1030000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030000		vux2code	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1316 ms	203856 KiB

selling_rna

// Src : Vux2Code
// Note : none
#include <bits/stdc++.h>
#define pq_rvs pll,vector<pll>,greater<pll>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

struct Edge {ll u, v, w;};

const ll alp = 4;
const vector <ll> emptyVec = {};

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

struct PreTrie {
	struct Node {
		Node* next [alp];
		ll l, r;
		Node () {
			for (int i = 0; i < alp; i ++) next [i] = NULL;
			l = -1; r = -1;
		}
	};
	Node* root; 
	PreTrie () {
		root = new Node ();
	}
	void add (string x, ll y) {
		Node* pos = root;
		for (int i = 0; i < x. size (); i ++) {
			if (pos -> next [enc (x [i])] == NULL) pos -> next [enc (x [i])] = new Node ();
			pos = pos -> next [enc (x [i])];
			if (pos -> l == -1) pos -> l = y;
			pos -> r = max (pos -> r, y);
		}
	}
	pll fin (string x) {
		Node* pos = root;
		for (int i = 0; i < x. size (); i ++) {
			if (pos -> next [enc (x [i])] == NULL) return {-1, -1};
			pos = pos -> next [enc (x [i])];
		}
		return {pos -> l, pos -> r};
	}
};

struct SufTrie {
	struct Node {
		Node* next [alp];
		vector <ll> vec;
		Node () {
			for (int i = 0; i < alp; i ++) next [i] = NULL;
			vec. clear ();
		}
	};
	Node* root; 
	SufTrie () {
		root = new Node ();
	}
	void add (string x, ll y) {
		Node* pos = root;
		for (int i = x. size () - 1; i >= 0; i --) {
			if (pos -> next [enc (x [i])] == NULL) pos -> next [enc (x [i])] = new Node ();
			pos = pos -> next [enc (x [i])];
			pos -> vec. push_back (y);
		}
	}
	vector <ll> fin (string x) {
		Node* pos = root;
		for (int i = x. size () - 1; i >= 0; i --) {
			if (pos -> next [enc (x [i])] == NULL) return emptyVec;
			pos = pos -> next [enc (x [i])];
		}
		return pos ->vec;
	}
};

const ll maxN = 2e5 + 5, inf64 = 1e18, mod = 1e9 + 7, maxLog = 20;
ll t = 1;

ll n, m;
string s [maxN], p, q;
PreTrie pre;
SufTrie suf;
vector <ll> tmp;
pll tmpLR;

void solve () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> s [i];
	sort (s + 1, s + n + 1);
	for (int i = 1; i <= n; i ++) {
		pre. add (s [i], i);
		suf. add (s [i], i);
	}
	for (int i = 1; i <= m; i ++) {
		cin >> p >> q;
		tmpLR = pre. fin (p);
		tmp = suf. fin (q);
		cout << upper_bound (tmp. begin (), tmp. end (), tmpLR. second) - lower_bound (tmp. begin (), tmp. end (), tmpLR. first) << '\n';
	}
}

int main (){
	ios::sync_with_stdio (0);
	cin. tie (0);
	cout. tie (0);
	// #define task "chill"
	// freopen (task".inp", "r", stdin);
	// freopen (task".out", "w", stdout);
	//cin >> t;
    while (t --) solve ();
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void PreTrie::add(std::string, ll)':
selling_rna.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int i = 0; i < x. size (); i ++) {
      |                   ~~^~~~~~~~~~~~
selling_rna.cpp: In member function 'pll PreTrie::fin(std::string)':
selling_rna.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < x. size (); i ++) {
      |                   ~~^~~~~~~~~~~~

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