oj.uz

Submission #20989

# Submission time Handle Problem Language Result Execution time Memory
20989 2017-03-27T08:17:44 Z model_code Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 309 ms 584408 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

const int MAXN = 100000;
const int MAXM = 100000;
const int KIND_CHAR = 4;

struct segtree
{
	static const int DEPTH = 18;
	static const int N = 1 << DEPTH;
	int data[2 * N];

	void init()
	{
		for (int i = 0; i < 2 * N; ++i) data[i] = 0;
	}
	void append(int p, int v)
	{
		p += N;
		while (p) {
			data[p] += v;
			p >>= 1;
		}
	}
	int query(int L, int R)
	{
		int ret = 0;
		L += N; R += N;
		while (L < R) {
			if (L & 1) ret += data[L++];
			if (R & 1) ret += data[--R];
			L >>= 1; R >>= 1;
		}
		return ret;
	}
};
struct node
{
	node *next[KIND_CHAR];
	vector<int> val;
};

node pool[10000000]; int pLast = 0;

node *alloc()
{
	node *ret = &(pool[pLast++]);
	for (int i = 0; i < KIND_CHAR; ++i) ret->next[i] = nullptr;
	return ret;
}

int N, M;
string A[MAXN];
string P[MAXM], Q[MAXM];
char in[1010101];

node *trie, *trie_rev;

void append(node *nd, string &str, int v)
{
	for (int i = 0; i < str.size(); ++i) {
		int c = str[i];
		if (!nd->next[c]) nd->next[c] = alloc();
		nd = nd->next[c];
	}
	nd->val.push_back(v);
}

int px[MAXN], py[MAXN], leftx[MAXM], rightx[MAXM], lefty[MAXM], righty[MAXM];
int ret[MAXM];
segtree seg;

void visit(node *nd, int *idx, int *p, int *lf, int *rg)
{
	if (nd == nullptr) return;
	for (int v : nd->val) {
		if (v < 0) {
			v = ~v;
			lf[v] = *idx;
		}
	}
	for (int v : nd->val) {
		if (v >= 0) {
			p[v] = (*idx)++;
		}
	}
	for (int i = 0; i < KIND_CHAR; ++i) visit(nd->next[i], idx, p, lf, rg);
	for (int v : nd->val) {
		if (v < 0) {
			v = ~v;
			rg[v] = *idx;
		}
	}
}
int trans(char c)
{
	if (c == 'A') return 0;
	if (c == 'U') return 1;
	if (c == 'G') return 2;
	if (c == 'C') return 3;
}
struct action
{
	int pos;
	int type;
	int left, right;
	action(int pos = 0, int type = 0, int left = 0, int right = 0) : pos(pos), type(type), left(left), right(right){}
};
inline bool operator<(const action& a, const action& b)
{
	return a.pos < b.pos || (a.pos == b.pos && a.type < b.type);
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%s", in); A[i] = in;
		for (char& c : A[i]) c = trans(c);
	}
	for (int i = 0; i < M; ++i) {
		scanf("%s", in); P[i] = in;
		for (char& c : P[i]) c = trans(c);
		scanf("%s", in); Q[i] = in;
		for (char& c : Q[i]) c = trans(c);
	}
	trie = alloc(); trie_rev = alloc();
	for (int i = 0; i < N; ++i) {
		append(trie, A[i], i);
		reverse(A[i].begin(), A[i].end());
		append(trie_rev, A[i], i);
	}
	for (int i = 0; i < M; ++i) {
		append(trie, P[i], ~i);
		reverse(Q[i].begin(), Q[i].end());
		append(trie_rev, Q[i], ~i);
	}
	int idx = 0; visit(trie, &idx, px, leftx, rightx);
	idx = 0; visit(trie_rev, &idx, py, lefty, righty);
	for (int i = 0; i < M; ++i) ret[i] = 0;
	vector<action> v; const int INFT = 1000000;
	for (int i = 0; i < N; ++i) {
		v.push_back(action(px[i], INFT, py[i]));
	}
	for (int i = 0; i < M; ++i) {
		v.push_back(action(leftx[i], ~i, lefty[i], righty[i]));
		v.push_back(action(rightx[i], i, lefty[i], righty[i]));
	}
	sort(v.begin(), v.end());
	seg.init();
	for (action& a : v) {
		if (a.type == INFT) {
			seg.append(a.left, 1);
		} else if (a.type >= 0) {
			ret[a.type] += seg.query(a.left, a.right);
		} else {
			ret[~a.type] -= seg.query(a.left, a.right);
		}
	}
	for (int i = 0; i < M; ++i) printf("%d\n", ret[i]);
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void append(node*, std::__cxx11::string&, int)':
selling_rna.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < str.size(); ++i) {
                    ^
selling_rna.cpp: In function 'int trans(char)':
selling_rna.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:119:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
selling_rna.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", in); A[i] = in;
                  ^
selling_rna.cpp:125:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", in); P[i] = in;
                  ^
selling_rna.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", in); Q[i] = in;
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 563952 KB Output is correct
2 Correct 96 ms 563952 KB Output is correct
3 Correct 116 ms 563952 KB Output is correct
4 Correct 96 ms 563952 KB Output is correct
5 Correct 106 ms 563952 KB Output is correct
6 Correct 146 ms 563952 KB Output is correct
7 Correct 119 ms 563952 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 568576 KB Output is correct
2 Correct 286 ms 568844 KB Output is correct
3 Correct 263 ms 568820 KB Output is correct
4 Correct 259 ms 568840 KB Output is correct
5 Correct 309 ms 567696 KB Output is correct
6 Correct 293 ms 567704 KB Output is correct
7 Correct 196 ms 570160 KB Output is correct
8 Correct 259 ms 570828 KB Output is correct
9 Correct 259 ms 570936 KB Output is correct
10 Correct 196 ms 568300 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 571560 KB Output is correct
2 Correct 146 ms 567868 KB Output is correct
3 Correct 146 ms 568200 KB Output is correct
4 Correct 176 ms 567764 KB Output is correct
5 Correct 129 ms 567860 KB Output is correct
6 Correct 159 ms 568100 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 563952 KB Output is correct
2 Correct 96 ms 563952 KB Output is correct
3 Correct 116 ms 563952 KB Output is correct
4 Correct 96 ms 563952 KB Output is correct
5 Correct 106 ms 563952 KB Output is correct
6 Correct 146 ms 563952 KB Output is correct
7 Correct 119 ms 563952 KB Output is correct
8 Correct 269 ms 568576 KB Output is correct
9 Correct 286 ms 568844 KB Output is correct
10 Correct 263 ms 568820 KB Output is correct
11 Correct 259 ms 568840 KB Output is correct
12 Correct 309 ms 567696 KB Output is correct
13 Correct 293 ms 567704 KB Output is correct
14 Correct 196 ms 570160 KB Output is correct
15 Correct 259 ms 570828 KB Output is correct
16 Correct 259 ms 570936 KB Output is correct
17 Correct 196 ms 568300 KB Output is correct
18 Correct 159 ms 571560 KB Output is correct
19 Correct 146 ms 567868 KB Output is correct
20 Correct 146 ms 568200 KB Output is correct
21 Correct 176 ms 567764 KB Output is correct
22 Correct 129 ms 567860 KB Output is correct
23 Correct 159 ms 568100 KB Output is correct
24 Correct 269 ms 570564 KB Output is correct
25 Correct 249 ms 572856 KB Output is correct
26 Correct 233 ms 569544 KB Output is correct
27 Correct 233 ms 570556 KB Output is correct
28 Correct 293 ms 584408 KB Output is correct
29 Correct 226 ms 578364 KB Output is correct