oj.uz

Submission #102236

# Submission time Handle Problem Language Result Execution time Memory
102236 2019-03-23T18:40:42 Z jasony123123 Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 1500 ms 163448 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/*************************JOI16_selling_rna***************************************/
int N, M;

int conv(char c) {
	if (c == 'A') return 0;
	if (c == 'C') return 1;
	if (c == 'U') return 2;
	return 3;
}

struct Node {
	int nxt[4];
	v<int> str;
	Node() { memset(nxt, -1, sizeof nxt); }
	v<int> getChildren() {
		v<int> chi;
		FOR(i, 0, 4) if (nxt[i] != -1) chi.push_back(nxt[i]);
		return chi;
	}
};

struct Trie {
	Node t[2000000];
	int tsz = 1;

	int dfstim = 0;
	int P[100001]; // for -(1-N)
	int L[100001], R[100001]; // for +(1-M)

	void addTrieNode(string &s, int num) {
		int cur = 0;
		for (char &cc : s) {
			int c = conv(cc);
			if (t[cur].nxt[c] == -1)
				t[cur].nxt[c] = tsz++;
			cur = t[cur].nxt[c];
		}
		t[cur].str.push_back(num);
	}

	void dfs(int cur) {
		if (t[cur].str.size()>0)
			dfstim++;
		for (int x : t[cur].str)
			if (x < 0) P[abs(x)] = dfstim;
			else L[x] = dfstim;

		v<int> adj = t[cur].getChildren();
		for (auto nex : adj)
			dfs(nex);

		if (t[cur].str.size()>0)
			dfstim++;
		for (int x : t[cur].str)
			if (x > 0) R[x] = dfstim;
	}
} tfor, trev;

int main() {
	io();
	cin >> N >> M;
	FORE(i, 1, N) {
		string s; cin >> s;
		tfor.addTrieNode(s, -i);
		reverse(all(s));
		trev.addTrieNode(s, -i);
	}
	FORE(i, 1, M) {
		string p, q; cin >> p >> q;
		tfor.addTrieNode(p, i);
		reverse(all(q));
		trev.addTrieNode(q, i);
	}
	tfor.dfs(0);
	trev.dfs(0);

	//FORE(i, 1, N) {
	//	printf("org str; point @ (%d, %d) \n", tfor.P[i], trev.P[i]);
	//}
	//FORE(i, 1, M) {
	//	printf("org query; rect @ x(%d, %d), y(%d, %d) \n", tfor.L[i], tfor.R[i], trev.L[i], trev.R[i]);
	//}
	FORE(i, 1, M) {
		int ans = 0;
		FORE(k, 1, N) if (tfor.L[i] <= tfor.P[k] && tfor.P[k] <= tfor.R[i] && trev.L[i] <= trev.P[k] && trev.P[k] <= trev.R[i])
			ans++;
		cout << ans << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 157008 KB Output is correct
2 Correct 146 ms 156892 KB Output is correct
3 Correct 146 ms 156920 KB Output is correct
4 Correct 150 ms 156920 KB Output is correct
5 Correct 152 ms 156948 KB Output is correct
6 Correct 148 ms 156940 KB Output is correct
7 Correct 142 ms 157020 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 161736 KB Output is correct
2 Correct 501 ms 161600 KB Output is correct
3 Correct 391 ms 161616 KB Output is correct
4 Correct 453 ms 161628 KB Output is correct
5 Correct 444 ms 160396 KB Output is correct
6 Correct 451 ms 160376 KB Output is correct
7 Correct 190 ms 162808 KB Output is correct
8 Correct 396 ms 163448 KB Output is correct
9 Correct 377 ms 163364 KB Output is correct
10 Correct 302 ms 160828 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 159904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 157008 KB Output is correct
2 Correct 146 ms 156892 KB Output is correct
3 Correct 146 ms 156920 KB Output is correct
4 Correct 150 ms 156920 KB Output is correct
5 Correct 152 ms 156948 KB Output is correct
6 Correct 148 ms 156940 KB Output is correct
7 Correct 142 ms 157020 KB Output is correct
8 Correct 339 ms 161736 KB Output is correct
9 Correct 501 ms 161600 KB Output is correct
10 Correct 391 ms 161616 KB Output is correct
11 Correct 453 ms 161628 KB Output is correct
12 Correct 444 ms 160396 KB Output is correct
13 Correct 451 ms 160376 KB Output is correct
14 Correct 190 ms 162808 KB Output is correct
15 Correct 396 ms 163448 KB Output is correct
16 Correct 377 ms 163364 KB Output is correct
17 Correct 302 ms 160828 KB Output is correct
18 Execution timed out 1567 ms 159904 KB Time limit exceeded
19 Halted 0 ms 0 KB -