oj.uz

Submission #332701

# Submission time Handle Problem Language Result Execution time Memory
332701 2020-12-03T03:41:30 Z 8e7 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 293 ms 198508 KB 
//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

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 159868 KB Output is correct
2 Correct 226 ms 151532 KB Output is correct
3 Correct 243 ms 157932 KB Output is correct
4 Correct 231 ms 150160 KB Output is correct
5 Correct 288 ms 195540 KB Output is correct
6 Correct 293 ms 198508 KB Output is correct
7 Correct 64 ms 5740 KB Output is correct
8 Correct 242 ms 117100 KB Output is correct
9 Correct 206 ms 99180 KB Output is correct
10 Correct 164 ms 95792 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7164 KB Output is correct
2 Correct 23 ms 6252 KB Output is correct
3 Correct 28 ms 6764 KB Output is correct
4 Correct 21 ms 5896 KB Output is correct
5 Correct 24 ms 6564 KB Output is correct
6 Correct 29 ms 7072 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2796 KB Output is correct
8 Correct 234 ms 159868 KB Output is correct
9 Correct 226 ms 151532 KB Output is correct
10 Correct 243 ms 157932 KB Output is correct
11 Correct 231 ms 150160 KB Output is correct
12 Correct 288 ms 195540 KB Output is correct
13 Correct 293 ms 198508 KB Output is correct
14 Correct 64 ms 5740 KB Output is correct
15 Correct 242 ms 117100 KB Output is correct
16 Correct 206 ms 99180 KB Output is correct
17 Correct 164 ms 95792 KB Output is correct
18 Correct 30 ms 7164 KB Output is correct
19 Correct 23 ms 6252 KB Output is correct
20 Correct 28 ms 6764 KB Output is correct
21 Correct 21 ms 5896 KB Output is correct
22 Correct 24 ms 6564 KB Output is correct
23 Correct 29 ms 7072 KB Output is correct
24 Correct 220 ms 130796 KB Output is correct
25 Correct 228 ms 132896 KB Output is correct
26 Correct 209 ms 128748 KB Output is correct
27 Correct 226 ms 129516 KB Output is correct
28 Correct 159 ms 28880 KB Output is correct
29 Correct 86 ms 11884 KB Output is correct