oj.uz

Submission #242025

# Submission time Handle Problem Language Result Execution time Memory
242025 2020-06-26T14:43:11 Z BamiTorabi Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 247 ms 76408 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[maxM], 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['U'] = 0;
	MAPPA['C'] = 1;
	MAPPA['G'] = 2;
	MAPPA['A'] = 3;
	int n, q; scanf("%d %d\n", &n, &q);
	int N = 0, curr;
	for (int i = 0; i < n; 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++){
		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++)
		printf("%d\n", ans[i]);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:63:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%d %d\n", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51192 KB Output is correct
2 Correct 35 ms 51200 KB Output is correct
3 Correct 35 ms 51328 KB Output is correct
4 Correct 33 ms 51200 KB Output is correct
5 Correct 37 ms 51320 KB Output is correct
6 Correct 33 ms 51200 KB Output is correct
7 Correct 34 ms 51200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 57336 KB Output is correct
2 Correct 189 ms 61392 KB Output is correct
3 Correct 237 ms 76408 KB Output is correct
4 Correct 247 ms 75768 KB Output is correct
5 Correct 187 ms 67320 KB Output is correct
6 Correct 196 ms 67448 KB Output is correct
7 Correct 205 ms 64760 KB Output is correct
8 Correct 246 ms 70392 KB Output is correct
9 Correct 245 ms 69368 KB Output is correct
10 Correct 171 ms 64120 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 53204 KB Output is correct
2 Correct 55 ms 52856 KB Output is correct
3 Correct 62 ms 52980 KB Output is correct
4 Correct 54 ms 52472 KB Output is correct
5 Correct 55 ms 52472 KB Output is correct
6 Correct 61 ms 52728 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51192 KB Output is correct
2 Correct 35 ms 51200 KB Output is correct
3 Correct 35 ms 51328 KB Output is correct
4 Correct 33 ms 51200 KB Output is correct
5 Correct 37 ms 51320 KB Output is correct
6 Correct 33 ms 51200 KB Output is correct
7 Correct 34 ms 51200 KB Output is correct
8 Correct 197 ms 57336 KB Output is correct
9 Correct 189 ms 61392 KB Output is correct
10 Correct 237 ms 76408 KB Output is correct
11 Correct 247 ms 75768 KB Output is correct
12 Correct 187 ms 67320 KB Output is correct
13 Correct 196 ms 67448 KB Output is correct
14 Correct 205 ms 64760 KB Output is correct
15 Correct 246 ms 70392 KB Output is correct
16 Correct 245 ms 69368 KB Output is correct
17 Correct 171 ms 64120 KB Output is correct
18 Correct 58 ms 53204 KB Output is correct
19 Correct 55 ms 52856 KB Output is correct
20 Correct 62 ms 52980 KB Output is correct
21 Correct 54 ms 52472 KB Output is correct
22 Correct 55 ms 52472 KB Output is correct
23 Correct 61 ms 52728 KB Output is correct
24 Correct 196 ms 62096 KB Output is correct
25 Correct 204 ms 63352 KB Output is correct
26 Correct 191 ms 61560 KB Output is correct
27 Correct 227 ms 74360 KB Output is correct
28 Correct 234 ms 66040 KB Output is correct
29 Correct 181 ms 58104 KB Output is correct