oj.uz

Submission #102242

# Submission time Handle Problem Language Result Execution time Memory
102242 2019-03-23T18:59:20 Z jasony123123 Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 477 ms 329912 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***************************************/
const int MAXTRIE = 4000009;
const int MAXNM = 100009;
const int L = 200009; 
int N, M, ans[MAXNM];

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[MAXTRIE];
	int tsz = 1;

	int dfstim = 0;
	int P[MAXNM]; // for -(1-N)
	int L[MAXNM], R[MAXNM]; // 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;

struct events {
	int x, y, fl;
	events(int _x, int _y, int _fl) : x(_x), y(_y), fl(_fl) {}
};

int bit[L + 1];
void upd(int k, int val) {
	for (k++; k <= L; k += (k&-k))
		bit[k] += val;
}
int query(int k) {
	int temp = 0;
	for (k++; k > 0; k -= (k&-k))
		temp += bit[k];
	return temp;
}

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";
	//}

	v<events> alle;
	alle.reserve(N + 4 * M);
	FORE(i, 1, N)
		alle.push_back(events(tfor.P[i], trev.P[i], INT_MIN));
	FORE(i, 1, M) {
		alle.push_back(events(tfor.R[i], trev.R[i], +i));
		alle.push_back(events(tfor.L[i] - 1, trev.R[i], -i));
		alle.push_back(events(tfor.R[i], trev.L[i] - 1, -i));
		alle.push_back(events(tfor.L[i] - 1, trev.L[i] - 1, +i));
	}
	sort(all(alle), [](events &a, events &b) {
		return mp(a.x, a.fl) < mp(b.x, b.fl);
	});

	for (auto e : alle) {
		if (e.fl == INT_MIN)
			upd(e.y, 1);
		else if (e.fl < 0)
			ans[abs(e.fl)] -= query(e.y);
		else
			ans[e.fl] += query(e.y);
	}

	FORE(i, 1, M)
		cout << ans[i] << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 313464 KB Output is correct
2 Correct 262 ms 313592 KB Output is correct
3 Correct 265 ms 313592 KB Output is correct
4 Correct 291 ms 313464 KB Output is correct
5 Correct 287 ms 313608 KB Output is correct
6 Correct 275 ms 313464 KB Output is correct
7 Correct 276 ms 313720 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 314388 KB Output is correct
2 Correct 430 ms 314720 KB Output is correct
3 Correct 421 ms 314616 KB Output is correct
4 Correct 461 ms 314748 KB Output is correct
5 Correct 464 ms 314876 KB Output is correct
6 Correct 477 ms 314872 KB Output is correct
7 Correct 331 ms 314460 KB Output is correct
8 Correct 404 ms 314488 KB Output is correct
9 Correct 398 ms 314704 KB Output is correct
10 Correct 357 ms 314568 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 319092 KB Output is correct
2 Correct 312 ms 317332 KB Output is correct
3 Correct 309 ms 318660 KB Output is correct
4 Correct 316 ms 317816 KB Output is correct
5 Correct 307 ms 317380 KB Output is correct
6 Correct 318 ms 318584 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 313464 KB Output is correct
2 Correct 262 ms 313592 KB Output is correct
3 Correct 265 ms 313592 KB Output is correct
4 Correct 291 ms 313464 KB Output is correct
5 Correct 287 ms 313608 KB Output is correct
6 Correct 275 ms 313464 KB Output is correct
7 Correct 276 ms 313720 KB Output is correct
8 Correct 443 ms 314388 KB Output is correct
9 Correct 430 ms 314720 KB Output is correct
10 Correct 421 ms 314616 KB Output is correct
11 Correct 461 ms 314748 KB Output is correct
12 Correct 464 ms 314876 KB Output is correct
13 Correct 477 ms 314872 KB Output is correct
14 Correct 331 ms 314460 KB Output is correct
15 Correct 404 ms 314488 KB Output is correct
16 Correct 398 ms 314704 KB Output is correct
17 Correct 357 ms 314568 KB Output is correct
18 Correct 308 ms 319092 KB Output is correct
19 Correct 312 ms 317332 KB Output is correct
20 Correct 309 ms 318660 KB Output is correct
21 Correct 316 ms 317816 KB Output is correct
22 Correct 307 ms 317380 KB Output is correct
23 Correct 318 ms 318584 KB Output is correct
24 Correct 437 ms 319984 KB Output is correct
25 Correct 463 ms 322680 KB Output is correct
26 Correct 405 ms 319224 KB Output is correct
27 Correct 437 ms 319952 KB Output is correct
28 Correct 444 ms 329912 KB Output is correct
29 Correct 411 ms 327808 KB Output is correct