oj.uz

Submission #102238

# Submission time Handle Problem Language Result Execution time Memory
102238 2019-03-23T18:42:40 Z jasony123123 Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 1500 ms 315860 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[4000009];
	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 272 ms 313464 KB Output is correct
2 Correct 274 ms 313588 KB Output is correct
3 Correct 270 ms 313592 KB Output is correct
4 Correct 265 ms 313692 KB Output is correct
5 Correct 266 ms 313592 KB Output is correct
6 Correct 271 ms 313580 KB Output is correct
7 Correct 273 ms 313592 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 314240 KB Output is correct
2 Correct 567 ms 314360 KB Output is correct
3 Correct 496 ms 314148 KB Output is correct
4 Correct 541 ms 314384 KB Output is correct
5 Correct 605 ms 314492 KB Output is correct
6 Correct 583 ms 314236 KB Output is correct
7 Correct 347 ms 314008 KB Output is correct
8 Correct 522 ms 314104 KB Output is correct
9 Correct 490 ms 314124 KB Output is correct
10 Correct 379 ms 313848 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 313464 KB Output is correct
2 Correct 274 ms 313588 KB Output is correct
3 Correct 270 ms 313592 KB Output is correct
4 Correct 265 ms 313692 KB Output is correct
5 Correct 266 ms 313592 KB Output is correct
6 Correct 271 ms 313580 KB Output is correct
7 Correct 273 ms 313592 KB Output is correct
8 Correct 467 ms 314240 KB Output is correct
9 Correct 567 ms 314360 KB Output is correct
10 Correct 496 ms 314148 KB Output is correct
11 Correct 541 ms 314384 KB Output is correct
12 Correct 605 ms 314492 KB Output is correct
13 Correct 583 ms 314236 KB Output is correct
14 Correct 347 ms 314008 KB Output is correct
15 Correct 522 ms 314104 KB Output is correct
16 Correct 490 ms 314124 KB Output is correct
17 Correct 379 ms 313848 KB Output is correct
18 Execution timed out 1587 ms 315860 KB Time limit exceeded
19 Halted 0 ms 0 KB -