Submission #26014

#	Time	Username	Problem	Language	Result	Execution time	Memory
26014		gabrielsimoes	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	309 ms	162544 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40