oj.uz

Submission #159954

# Submission time Handle Problem Language Result Execution time Memory
159954 2019-10-25T14:20:02 Z iefnah06 Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 415 ms 181340 KB 
#include <bits/stdc++.h>
using namespace std;

int toInt(char c) {
	static const char alpha[] = "AGCU";
	int res = 0;
	for (; alpha[res] != c; res++);
	return res;
}

const int MAXN = 1.1e5;
const int MAXQ = 1.1e5;
int N, Q;

const int MAXL = 1.1e5;
char S[MAXL];

struct trie {
	trie* ch[4];
	int st, en;
};
trie* ROOTS[2];
trie* tnull;
void initTrie() {
	for (int flip = 0; flip < 2; flip++) {
		ROOTS[flip] = new trie();
	}
	tnull = new trie();
}

trie* insert(int len, trie* r) {
	for (int i = 0; i < len; i++) {
		int c = S[i];
		if (r->ch[c] == NULL) {
			r->ch[c] = new trie();
		}
		r = r->ch[c];
	}
	return r;
}

trie* query(int len, trie* r) {
	for (int i = 0; i < len; i++) {
		int c = S[i];
		if (r->ch[c] == NULL) {
			return tnull;
		}
		r = r->ch[c];
	}
	return r;
}

trie* locs[MAXN][2];

void dfs(trie* r, int& ind) {
	if (r == NULL) return;
	r->st = ind++;
	for (int c = 0; c < 4; c++) {
		dfs(r->ch[c], ind);
	}
	r->en = ind;
}

const int MAXV = 2.1e6;
int coords[MAXN][2];
int V[2] = {0, 0};
vector<int> pts[MAXV];

struct seg {
	seg* ch[2];
	int val;
};
seg* null;
void initSeg() {
	null = new seg();
	null->ch[0] = null->ch[1] = null;
	null->val = 0;
}

seg* segs[MAXV];

seg* update(int p, seg* r, int x = 0, int y = V[1]) {
	seg* n = new seg(*r);
	n->val++;
	if (y - x > 1) {
		int z = (x + y) / 2;
		if (p < z) {
			n->ch[0] = update(p, r->ch[0], x, z);
		} else {
			n->ch[1] = update(p, r->ch[1], z, y);
		}
	}
	return n;
}

int query(int l, int r, seg* n, int x = 0, int y = V[1]) {
	int res = 0;
	if (n != null) {
		if (l <= x && y <= r) {
			res = n->val;
		} else {
			int z = (x + y) / 2;
			if (l < z) {
				res += query(l, r, n->ch[0], x, z);
			}
			if (z < r) {
				res += query(l, r, n->ch[1], z, y);
			}
		}
	}
	return res;
}

bool inRange(int a, int mi, int ma) {
	return mi <= a && a < ma;
}

int querySlow(int xlo, int xhi, int ylo, int yhi) {
	int res = 0;
	for (int i = 0; i < N; i++) {
		res += inRange(coords[i][0], xlo, xhi) && inRange(coords[i][1], ylo, yhi);
	}
	return res;
}

int query(int xlo, int xhi, int ylo, int yhi) {
	assert(xlo <= xhi && ylo <= yhi);
//	return querySlow(xlo, xhi, ylo, yhi);
	return query(ylo, yhi, segs[xhi]) - query(ylo, yhi, segs[xlo]);
}

int main() {
	scanf("%d %d", &N, &Q);
	initTrie();
	for (int i = 0; i < N; i++) {
		scanf("%s", S);
		int len = int(strlen(S));
		for (int j = 0; j < len; j++) {
			S[j] = toInt(S[j]);
		}
		for (int flip = 0; flip < 2; flip++) {
			locs[i][flip] = insert(len, ROOTS[flip]);
			reverse(S, S + len);
		}
	}

	for (int flip = 0; flip < 2; flip++) {
		int ind = 0;
		dfs(ROOTS[flip], ind);
	}

	for (int i = 0; i < N; i++) {
		for (int flip = 0; flip < 2; flip++) {
			coords[i][flip] = locs[i][flip]->st;
			V[flip] = max(V[flip], coords[i][flip] + 1);
		}
		pts[coords[i][0]].push_back(coords[i][1]);
	}

	initSeg();
	segs[0] = null;
	for (int x = 0; x < V[0]; x++) {
		segs[x+1] = segs[x];
		for (size_t i = 0; i < pts[x].size(); i++) {
			int y = pts[x][i];
			assert(y < V[1]);
			segs[x+1] = update(y, segs[x+1]);
		}
	}

	for (int q = 0; q < Q; q++) {
		trie* Slocs[2];
		for (int flip = 0; flip < 2; flip++) {
			scanf("%s", S);
			int len = int(strlen(S));
			for (int j = 0; j < len; j++) {
				S[j] = toInt(S[j]);
			}
			if (flip) {
				reverse(S, S + len);
			}
			Slocs[flip] = query(len, ROOTS[flip]);
		}

		int ans = query(Slocs[0]->st, Slocs[0]->en, Slocs[1]->st, Slocs[1]->en); 
		printf("%d\n", ans);
	}

	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
   ~~~~~^~~~~~~~~
selling_rna.cpp:174:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", S);
    ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49756 KB Output is correct
2 Correct 47 ms 49656 KB Output is correct
3 Correct 48 ms 49760 KB Output is correct
4 Correct 48 ms 49868 KB Output is correct
5 Correct 47 ms 49784 KB Output is correct
6 Correct 48 ms 49632 KB Output is correct
7 Correct 47 ms 49656 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 147952 KB Output is correct
2 Correct 272 ms 145056 KB Output is correct
3 Correct 291 ms 161656 KB Output is correct
4 Correct 415 ms 157560 KB Output is correct
5 Correct 363 ms 179576 KB Output is correct
6 Correct 373 ms 181340 KB Output is correct
7 Correct 116 ms 56056 KB Output is correct
8 Correct 288 ms 131728 KB Output is correct
9 Correct 243 ms 119800 KB Output is correct
10 Correct 196 ms 115704 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 58104 KB Output is correct
2 Correct 94 ms 63864 KB Output is correct
3 Correct 101 ms 66680 KB Output is correct
4 Correct 74 ms 56028 KB Output is correct
5 Correct 92 ms 61432 KB Output is correct
6 Correct 99 ms 64504 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49756 KB Output is correct
2 Correct 47 ms 49656 KB Output is correct
3 Correct 48 ms 49760 KB Output is correct
4 Correct 48 ms 49868 KB Output is correct
5 Correct 47 ms 49784 KB Output is correct
6 Correct 48 ms 49632 KB Output is correct
7 Correct 47 ms 49656 KB Output is correct
8 Correct 294 ms 147952 KB Output is correct
9 Correct 272 ms 145056 KB Output is correct
10 Correct 291 ms 161656 KB Output is correct
11 Correct 415 ms 157560 KB Output is correct
12 Correct 363 ms 179576 KB Output is correct
13 Correct 373 ms 181340 KB Output is correct
14 Correct 116 ms 56056 KB Output is correct
15 Correct 288 ms 131728 KB Output is correct
16 Correct 243 ms 119800 KB Output is correct
17 Correct 196 ms 115704 KB Output is correct
18 Correct 81 ms 58104 KB Output is correct
19 Correct 94 ms 63864 KB Output is correct
20 Correct 101 ms 66680 KB Output is correct
21 Correct 74 ms 56028 KB Output is correct
22 Correct 92 ms 61432 KB Output is correct
23 Correct 99 ms 64504 KB Output is correct
24 Correct 265 ms 136540 KB Output is correct
25 Correct 310 ms 136824 KB Output is correct
26 Correct 255 ms 135672 KB Output is correct
27 Correct 271 ms 145528 KB Output is correct
28 Correct 351 ms 126076 KB Output is correct
29 Correct 166 ms 84224 KB Output is correct