oj.uz

Submission #26014

# Submission time Handle Problem Language Result Execution time Memory
26014 2017-06-26T14:15:04 Z gabrielsimoes Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 309 ms 162544 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int MAXSZ = 1e5+1;
const int LIM = 1e6+1;

int trans(char a) {
	if (a == 'A') return 0;
	else if (a == 'U') return 1;
	else if (a == 'C') return 2;
	else if (a == 'G') return 3;
	else return -1;
}

int N, M;
pii l[2][MAXSZ], r[2][MAXSZ];

struct node {
	vector<pii> end;
	node* nxt[4];
	node() {nxt[0] = nxt[1] = nxt[2] = nxt[3] = 0;}
	
	void insert(char s[], pii p) {
		int x = trans(*s);
		if (x == -1)
			end.push_back(p);
		else {
			if (!nxt[x]) nxt[x] = new node();
			nxt[x]->insert(s+1, p);
		}
	}

	int dfs(pii to[2][MAXSZ], int t = 0) {
		if (!end.empty()) {
			++t;
			for (pii p : end)
				to[p.first][p.second].first = t;
		}

		for (int i = 0; i < 4; i++)
			if (nxt[i]) t = nxt[i]->dfs(to, t);

		for (pii p : end)
			to[p.first][p.second].second = t;

		return t;
	}
};

struct bit {
	int sz;
	vector<int> v;

	bit (int sz) : sz(sz), v(sz+1, 0) {};
	void upd(int x, int d) {while (x < sz) v[x]+=d, x += x&-x;}
	int query(int x) {int ret=0; while (x) ret+=v[x], x -= x&-x; return ret;}
} bb(2*MAXSZ);

enum type { pBegin = 1, tBegin = 2, pEnd = 3, tEnd = 4 };
struct event {
	type t;
	int pos;
	int i;
	event(type t, int pos, int i) : t(t), pos(pos), i(i) {};
	bool operator<(event& o) {
		if (this->pos != o.pos) return this->pos < o.pos;
		else return this->t < o.t;
	}
};

int ans[MAXSZ];
int main()
{
	char buf[LIM];
	node* treeL = new node(), * treeR = new node();

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		scanf("%s", &buf);
		int sz = strlen(buf);
 		treeL->insert(buf, pii(0,i));
 		reverse(buf, buf+sz);
 		treeR->insert(buf, pii(0,i));
	}

	for (int i = 0; i < M; i++) {
		scanf("%s", &buf);
 		treeL->insert(buf, pii(1,i));

 		scanf("%s", &buf);
		int sz = strlen(buf);
 		reverse(buf, buf+sz);
 		treeR->insert(buf, pii(1,i));
	}

	treeL->dfs(l);
	treeR->dfs(r);

	vector<event> ev;
	for (int i = 0; i < N; i++) 
		ev.push_back(event(tBegin, l[0][i].first, i));

	for (int i = 0; i < M; i++) {
		ev.push_back(event(pBegin, l[1][i].first, i));
		ev.push_back(event(pEnd, l[1][i].second, i));
	}

	sort(ev.begin(), ev.end());

	for (event p : ev) {
		if (p.t == pBegin)
			ans[p.i] -= bb.query(r[1][p.i].second) - bb.query(r[1][p.i].first-1);
		else if (p.t == pEnd)
			ans[p.i] += bb.query(r[1][p.i].second) - bb.query(r[1][p.i].first-1);
		else if (p.t == tBegin)
			bb.upd(r[0][p.i].first, 1);
		else
			bb.upd(r[0][p.i].first, -1);
	}

	for (int i = 0; i < M; i++) printf("%d\n", 	ans[i]);
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:81:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
   scanf("%s", &buf);
                   ^
selling_rna.cpp:89:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
   scanf("%s", &buf);
                   ^
selling_rna.cpp:92:20: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
    scanf("%s", &buf);
                    ^
selling_rna.cpp:78:24: 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:81:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &buf);
                    ^
selling_rna.cpp:89:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &buf);
                    ^
selling_rna.cpp:92:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", &buf);
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7180 KB Output is correct
2 Correct 0 ms 7180 KB Output is correct
3 Correct 0 ms 7184 KB Output is correct
4 Correct 0 ms 7180 KB Output is correct
5 Correct 0 ms 7184 KB Output is correct
6 Correct 0 ms 7180 KB Output is correct
7 Correct 0 ms 7184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 130940 KB Output is correct
2 Correct 189 ms 124544 KB Output is correct
3 Correct 226 ms 129444 KB Output is correct
4 Correct 243 ms 123488 KB Output is correct
5 Correct 309 ms 160256 KB Output is correct
6 Correct 256 ms 162544 KB Output is correct
7 Correct 96 ms 8160 KB Output is correct
8 Correct 176 ms 97292 KB Output is correct
9 Correct 216 ms 82832 KB Output is correct
10 Correct 109 ms 80548 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14396 KB Output is correct
2 Correct 19 ms 11372 KB Output is correct
3 Correct 36 ms 11792 KB Output is correct
4 Correct 23 ms 10908 KB Output is correct
5 Correct 33 ms 11348 KB Output is correct
6 Correct 39 ms 11944 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7180 KB Output is correct
2 Correct 0 ms 7180 KB Output is correct
3 Correct 0 ms 7184 KB Output is correct
4 Correct 0 ms 7180 KB Output is correct
5 Correct 0 ms 7184 KB Output is correct
6 Correct 0 ms 7180 KB Output is correct
7 Correct 0 ms 7184 KB Output is correct
8 Correct 229 ms 130940 KB Output is correct
9 Correct 189 ms 124544 KB Output is correct
10 Correct 226 ms 129444 KB Output is correct
11 Correct 243 ms 123488 KB Output is correct
12 Correct 309 ms 160256 KB Output is correct
13 Correct 256 ms 162544 KB Output is correct
14 Correct 96 ms 8160 KB Output is correct
15 Correct 176 ms 97292 KB Output is correct
16 Correct 216 ms 82832 KB Output is correct
17 Correct 109 ms 80548 KB Output is correct
18 Correct 26 ms 14396 KB Output is correct
19 Correct 19 ms 11372 KB Output is correct
20 Correct 36 ms 11792 KB Output is correct
21 Correct 23 ms 10908 KB Output is correct
22 Correct 33 ms 11348 KB Output is correct
23 Correct 39 ms 11944 KB Output is correct
24 Correct 216 ms 109820 KB Output is correct
25 Correct 226 ms 111792 KB Output is correct
26 Correct 213 ms 107824 KB Output is correct
27 Correct 199 ms 108484 KB Output is correct
28 Correct 206 ms 34828 KB Output is correct
29 Correct 109 ms 20648 KB Output is correct