Submission #332701

#	Time	Username	Problem	Language	Result	Execution time	Memory
332701		8e7	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	293 ms	198508 KiB

selling_rna

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#define ll long long
#define ff first
#define ss second
#define maxn 100005
#define mod 1000000007
#define zckorz ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
int cor[maxn], arr[maxn], ans[maxn];
struct node {
	char c;
	int cnt = 0, l, r;
	node * chi[4];
	vector<int> v;
	node(char ch) {
		c = ch, cnt = 0, l = 0, r = 0;
		for (int i = 0;i < 4;i++) chi[i] = NULL;
	}
	node() {
		c = ' ', cnt = 0, l = 0, r = 0;
		for (int i = 0;i < 4;i++) chi[i] = NULL;
	}
};
void add(node * cur, string &s, int ind, int x) {
	//cout << cur->c;
	if (ind == s.size() - 1) {
		cur->cnt++;
		cur->v.push_back(x);
		return;
	}
	//cout << s << " " << ind << endl;
	int nxt = s[ind + 1] - 'A';
	if (cur->chi[nxt] == NULL) {
		node * add = new node(s[ind + 1]);
		cur->chi[nxt] = add;
	}
	add(cur->chi[nxt], s, ind + 1, x);
}
void print(node * cur, int dep) {
	//cout << 7122 << endl;
	for (int i = 0;i < dep;i++) cout << " ";
	cout << cur->c << endl;
	for (int i = 0;i < 4;i++) {
		if (cur->chi[i] != NULL) {
			//cout << 11 << endl;
			print(cur->chi[i], dep + 1);
		}
	}
}

int ind = 0;
void dfs(node * cur) {
	cur->l = ind;
	for (int x:cur->v) {
		cor[x] = ind++;
	}
	for (int i = 0;i < 4;i++) {
		if (cur->chi[i] != NULL) {
			dfs(cur->chi[i]);
		}
	}
	cur->r = ind;
}
void dfs2(node * cur) {
	cur->l = ind;
	for (int x:cur->v) {
		arr[ind++] = cor[x];
	}
	for (int i = 0;i < 4;i++) {
		if (cur->chi[i] != NULL) {
			dfs2(cur->chi[i]);
		}
	}
	cur->r = ind;
}
pair<int, int> range(node * cur, string & s, int ind) {
	if (ind == s.size() - 1) {
		return make_pair(cur->l, cur->r);
	}
	int nxt = s[ind + 1] - 'A';
	if (cur->chi[nxt] == NULL) {
		return make_pair(-1, -1);
	} else {
		return range(cur->chi[nxt], s, ind + 1);
	}
}
node * pref = new node(), * suf = new node();

struct ev{
	int y, id;
	bool pos;
	ev(int b, int c, bool d) {
		y = b, id = c, pos = d;
	}
};
vector<ev> que[maxn];

int bit[maxn];
void modify(int ind, int val) {
	ind++;
	for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
int query(int ind) {
	ind++;
	if (ind < 0) return 0;
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
	return ret;
}
int main() {
	zckorz
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		for (int j = 0;j < s.size();j++) s[j] = (s[j] == 'G' ? 'B' : (s[j] == 'U' ? 'D' : s[j]));
		add(pref, s, -1, i);
		//cout << endl;
		reverse(s.begin(), s.end());
		add(suf, s, -1, i);
		//cout << endl;
	}
	dfs(pref);
	ind = 0;
	dfs2(suf);
	//for (int i = 0;i < n;i++) cout << arr[i] << " ";
	//cout << endl;
	for (int i = 0;i < m;i++) {
		string p, q;
		cin >> p >> q;
		for (int j = 0;j < p.size();j++) p[j] = (p[j] == 'G' ? 'B' : (p[j] == 'U' ? 'D' : p[j]));
		for (int j = 0;j < q.size();j++) q[j] = (q[j] == 'G' ? 'B' : (q[j] == 'U' ? 'D' : q[j]));
		reverse(q.begin(), q.end());
		pair<int, int> r1 = range(pref, p, -1), r2 = range(suf, q, -1);
		//cout << r2.ff << " " << r2.ss << " " << r1.ff << " " << r1.ss << endl;
		if (r1.ff == -1 || r2.ff == -1) {
			ans[i] = 0;
		} else {
			int l = r2.ff, r = r2.ss, x = r1.ff, y = r1.ss;

			que[r - 1].push_back(ev(y - 1, i, true));
			que[r - 1].push_back(ev(x - 1, i, false));
			if (l) que[l - 1].push_back(ev(y - 1, i, false));
			if (l) que[l - 1].push_back(ev(x - 1, i, true));
		}
	}
	for (int i = 0;i < n;i++) {
		modify(arr[i], 1);
		for (auto j:que[i]) {
			if (j.pos) {
				ans[j.id] += query(j.y);
			} else {
				ans[j.id] -= query(j.y);
			}
		}
	}
	for (int i = 0;i < m;i++) cout << ans[i] << "\n";
	//print(pref, 0);
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(node*, std::string&, int, int)':
selling_rna.cpp:32:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if (ind == s.size() - 1) {
      |      ~~~~^~~~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> range(node*, std::string&, int)':
selling_rna.cpp:83:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  if (ind == s.size() - 1) {
      |      ~~~~^~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int j = 0;j < s.size();j++) s[j] = (s[j] == 'G' ? 'B' : (s[j] == 'U' ? 'D' : s[j]));
      |                  ~~^~~~~~~~~~
selling_rna.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for (int j = 0;j < p.size();j++) p[j] = (p[j] == 'G' ? 'B' : (p[j] == 'U' ? 'D' : p[j]));
      |                  ~~^~~~~~~~~~
selling_rna.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for (int j = 0;j < q.size();j++) q[j] = (q[j] == 'G' ? 'B' : (q[j] == 'U' ? 'D' : q[j]));
      |                  ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40