oj.uz

Submission #242010

# Submission time Handle Problem Language Result Execution time Memory
242010 2020-06-26T13:52:11 Z BamiTorabi Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 129 ms 48340 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 43776 KB Output is correct
2 Correct 29 ms 43776 KB Output is correct
3 Correct 29 ms 43768 KB Output is correct
4 Correct 28 ms 43776 KB Output is correct
5 Correct 28 ms 43776 KB Output is correct
6 Correct 28 ms 43776 KB Output is correct
7 Correct 28 ms 43792 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 48340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 45780 KB Output is correct
2 Correct 51 ms 45176 KB Output is correct
3 Correct 54 ms 45428 KB Output is correct
4 Correct 49 ms 45176 KB Output is correct
5 Correct 53 ms 45048 KB Output is correct
6 Correct 58 ms 45304 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 43776 KB Output is correct
2 Correct 29 ms 43776 KB Output is correct
3 Correct 29 ms 43768 KB Output is correct
4 Correct 28 ms 43776 KB Output is correct
5 Correct 28 ms 43776 KB Output is correct
6 Correct 28 ms 43776 KB Output is correct
7 Correct 28 ms 43792 KB Output is correct
8 Incorrect 129 ms 48340 KB Output isn't correct
9 Halted 0 ms 0 KB -