Submission #1032635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032635		juicy	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	237 ms	286928 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, MAX = 2e6 + 5, C = 26;

struct Trie {
	int tot = 1;
	int nxt[MAX][C], ord[MAX], tout[MAX];

	int add(int p, char c) {
		if (!nxt[p][c - 'A']) {
			nxt[p][c - 'A'] = ++tot;
		}
		return nxt[p][c - 'A'];
	}

	void ins(const string &s) {
		int p = 1;
		for (char c : s) {
			p = add(p, c);
		}
	}

	int timer = 0;

	void dfs(int u) {
		ord[u] = ++timer;
		for (int i = 0; i < C; ++i) {
			if (nxt[u][i]) {
				dfs(nxt[u][i]);
			}
		}
		tout[u] = timer;
	}

	int search(const string &s) {
		int p = 1;
		for (char c : s) {
			if (!nxt[p][c - 'A']) {
				return 0;
			}
			p = nxt[p][c - 'A'];
		}
		return p;
	}
} pf, sf;

int n, m;
int ft[MAX], res[N];
string s[N];

void upd(int i, int x) {
	for (; i < MAX; i += i & -i) {
		ft[i] += x;
	}
}

int qry(int i) {
	int res = 0;
	for (; i; i -= i & -i) {
		res += ft[i];
	}
	return res;
}

int qry(int l, int r) {
	return qry(r) - qry(l - 1);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		pf.ins(s[i]);
		reverse(s[i].begin(), s[i].end());
		sf.ins(s[i]);
	}
	pf.dfs(1);
	sf.dfs(1);
	vector<array<int, 2>> pt;
	for (int i = 1; i <= n; ++i) {
		int y = sf.search(s[i]);
		reverse(s[i].begin(), s[i].end());
		int x = pf.search(s[i]);
		pt.push_back({pf.ord[x], sf.ord[y]});
	}
	vector<array<int, 4>> Queries;
	for (int i = 1; i <= m; ++i) {
		string P, Q; cin >> P >> Q;
		reverse(Q.begin(), Q.end());
		int p = pf.search(P), q = sf.search(Q);
		if (p && q) {
			int x = pf.ord[p], y = pf.tout[p], a = sf.ord[q], b = sf.tout[q];
			Queries.push_back({x - 1, a, b, -i});
			Queries.push_back({y, a, b, i});
		}
	}
	sort(Queries.begin(), Queries.end());
	sort(pt.begin(), pt.end());
	int j = 0;
	for (auto [x, u, v, id] : Queries) {
		while (j < pt.size() && pt[j][0] <= x) {
			upd(pt[j][1], 1);
			++j;
		} 
		if (id > 0) {
			res[id] += qry(u, v);
		} else {
			res[-id] -= qry(u, v);
		}
	}
	for (int i = 1; i <= m; ++i) {
		cout << res[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:111:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   while (j < pt.size() && pt[j][0] <= x) {
      |          ~~^~~~~~~~~~~

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