Submission #1086809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086809		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	179 ms	200788 KiB

selling_rna

#include<bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FOD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
#define ll long long 
#define ALL(a) a.begin(), a.end()
#define sz(a) a.size()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define el "\n"
#define bit(a, x) (a >> x & 1)
#define X first
#define Y second
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define uni(a) sort(ALL(a)), a.resize(unique(ALL(a)) - a.begin())
using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

const int maxn = 1e5 + 5;

string s[maxn];
int n, m;

int getint(char f) {
    if (f == 'A') return 0;
    if (f == 'G') return 1;
    if (f == 'C') return 2;
    return 3;
}

struct Trie{
	struct Node{
		Node* child[4];
		int cnt, maxx, minn;
		Node(){
			FOR(i, 0, 3) child[i] = NULL;
			maxx = -1e9;
			minn = 1e9;
		}
	};
		
	Node *root;
	int cur;
	Trie() : cur(0){
		root = new Node();
	};

	void add(string s, int id){
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) p -> child[c] = new Node();
				p = p -> child[c];
				p -> maxx = max(p -> maxx, id);
				p -> minn = min(p -> minn, id);
		}
	}

	pii query(string s){
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) return {-1, -1};
			p = p -> child[c];
		}
		return {p -> minn, p -> maxx};
		}
} trie;

struct InTrie{
	struct Node{
		Node *child[4];
		vi list;
		Node (){
			FOR(i, 0, 3) child[i] = NULL;
			list.clear();
		}
	};
	Node* root;
	int cur;
	InTrie() : cur(0){
		root = new Node();
	};

	void add(string s, int id){
		reverse(ALL(s));
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) p -> child[c] = new Node();
			p = p -> child[c];
			p -> list.pb(id);
		}
	}

	int query(string s, pii range){
		reverse(ALL(s));
		Node* p = root;
		for(auto f : s){
			int c = getint(f);
			if(p -> child[c] == NULL) return 0;
			p = p -> child[c];
		}
		int l = lower_bound(ALL(p -> list), range.X) - p -> list.begin();
		int r = upper_bound(ALL(p -> list), range.Y) - p -> list.begin() - 1;
		return r - l + 1;
	}
} trie1;

signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> n >> m;
	FOR(i, 1, n) cin >> s[i];
	sort(s + 1, s + n + 1);
	FOR(i, 1, n){
		trie.add(s[i], i);
		trie1.add(s[i], i);
	}
	while(m--){
		string p, q;
		cin >> p >> q;
		pii range = trie.query(p);
		if(range.X == -1) cout << 0;
		else cout << trie1.query(q, range);
		cout << el;
	}
	cerr << "Time elapsed: " << TIME << " s" << el;
}

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