제출 #242010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242010		BamiTorabi	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	129 ms	48340 KiB

selling_rna

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const int maxM = 2e6 + 5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

map <char, int> MAPPA;
int trie[maxM][4], num[maxN], ans[maxN];
int st[maxM], fn[maxM], TIME = 0;
pii pos[maxN];
vector <pii> quer[maxN];
string s[maxN], pre[maxN], suf[maxN];

void getstr(string& S, char C = '\n'){
	char ch;
	while ((ch = getchar()) != C)
		S += ch;
	return;
}

void LEVI(int v = 0){
	st[v] = TIME++;
	for (int i = 0; i < 4; i++)
		if (trie[v][i] != -1)
			LEVI(trie[v][i]);
	fn[v] = TIME;
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(trie, -1, sizeof trie);
	MAPPA['A'] = 0;
	MAPPA['C'] = 1;
	MAPPA['G'] = 2;
	MAPPA['U'] = 3;
	int n, q; cin >> n >> q;//scanf("%d %d\n", &n, &q);
	int N = 0, curr;
	for (int i = 0; i < n; i++){
		cin >> s[i]; //getstr(s[i]);
		curr = 0;
		for (char ch : s[i]){
			int c = MAPPA[ch];
			if (trie[curr][c] == -1)
				trie[curr][c] = ++N;
			curr = trie[curr][c];
		}
		num[i] = curr;
	}
	LEVI();
	for (int i = 0; i < n; i++)
		pos[i] = {st[num[i]], i};
	sort(pos, pos + n);
	for (int i = 0; i < q; i++){
		cin >> pre[i] >> suf[i];//getstr(pre[i], ' ');
		//getstr(suf[i]);
		reverse(suf[i].begin(), suf[i].end());
		curr = 0;
		for (char ch : pre[i]){
			curr = trie[curr][MAPPA[ch]];
			if (curr == -1)
				break;
		}
		if (curr != -1){
			int l = lower_bound(pos, pos + n, make_pair(st[curr], -MOD)) - pos;
			int r = lower_bound(pos, pos + n, make_pair(fn[curr], -MOD)) - pos;
			quer[l].push_back({-1, i});
			quer[r].push_back({+1, i});
		}
	}
	for (int i = 0; i < n; i++)
		reverse(s[i].begin(), s[i].end());
	memset(trie, -1, sizeof trie);
	memset(num, 0, sizeof num);
	N = 0;
	for (int i = 0; i <= n; i++){
		for (pii pp : quer[i]){
			int id, tmp; tie(tmp, id) = pp;
			curr = 0;
			for (char ch : suf[id]){
				curr = trie[curr][MAPPA[ch]];
				if (curr == -1)
					break;
			}
			if (curr != -1)
				ans[id] += tmp * num[curr];
		}
		if (i < n){
			curr = 0;
			for (char ch : s[pos[i].second]){
				int c = MAPPA[ch];
				if (trie[curr][c] == -1)
					trie[curr][c] = ++N;
				curr = trie[curr][c];
				num[curr]++;
			}
		}
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << "\n"; //printf("%d\n", ans[i]);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

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