Submission #776949

#	Time	Username	Problem	Language	Result	Execution time	Memory
776949		TeaTime	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	493 ms	446572 KiB

selling_rna

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <vector>
#include <ctime>
#include <random>
#include <cassert>
#include <tuple>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll AL = 26, SZ = 100'100;
int n, m, t = 0;
vector<string> vec;
struct query {
	string a, b;
};
vector<query> queries;

struct node {
	node* to[AL];
	int tin = 0, tout = 0;

	node() {
		for (int i = 0; i < AL; i++) {
			to[i] = 0;
		}
	}
};
node *pref_trie, *suf_trie;

node* ins(node* v, string s, bool srch = 0) {
	int i = 0;
	while (i < s.size()) {
		if (!v->to[s[i] - 'A']) {
			if (srch) return nullptr;
			v->to[s[i] - 'A'] = new node();
		}

		v = v->to[s[i] - 'A'];
		i++;
	}

	return v;
}

struct rect {
	ll x1, y1, x2, y2;
};

vector<pair<ll, ll>> coords;
vector<rect> rects;

void dfs(node* v) {
	t++;
	v->tin = t;

	for (auto adj : v->to) {
		if (adj) dfs(adj);
	}

	v->tout = t;
}

vector<ll> upds[SZ];
vector<tuple<ll, ll, ll>> scan[SZ];

ll seg[SZ * 4];
void upd(int v, int l, int r, int pos) {
	if (l == r - 1) {
		seg[v]++;
	} else {
		int mid = (l + r) / 2;
		if (pos < mid) {
			upd(v * 2 + 1, l, mid, pos);
		} else {
			upd(v * 2 + 2, mid, r, pos);
		}
		seg[v] = seg[v * 2 + 1] + seg[v * 2 + 2];
	}
}

ll ask(int v, int l, int r, int askl, int askr) {
	if (l >= askr || r <= askl) return 0;

	if (askl <= l && r <= askr) return seg[v];

	int mid = (l + r) / 2;
	return ask(v * 2 + 1, l, mid, askl, askr) + ask(v * 2 + 2, mid, r, askl, askr);
}

int main() {
	fastInp;

	cin >> n >> m;

	pref_trie = new node();
	suf_trie = new node();

	vec.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> vec[i];
		ins(pref_trie, vec[i]);
		string rv = vec[i];
		reverse(rv.begin(), rv.end());
		ins(suf_trie, rv);
	}

	dfs(pref_trie);
	t = 0;
	dfs(suf_trie);

	for (int i = 0; i < n; i++) {
		node* x = ins(pref_trie, vec[i]);
		string rv = vec[i];
		reverse(rv.begin(), rv.end());
		node* y = ins(suf_trie, rv);

		upds[x->tin].push_back(y->tin);
	}

	vector<ll> ans(m);
	vector<ll> add(m);
	for (int i = 0; i < m; i++) {
		string p, q;
		cin >> p >> q;
		queries.push_back({ p, q });
		reverse(q.begin(), q.end());
		node* x = ins(pref_trie, p, 1);
		node* y = ins(suf_trie, q, 1);
		if (!x || !y) continue;
		scan[x->tin - 1].push_back({ y->tin, y->tout, i });
		scan[x->tout].push_back({ y->tin, y->tout, i });
	}

	for (int i = 0; i < SZ; i++) {
		for (auto c : upds[i]) {
			upd(0, 0, SZ, c);
		}

		for (auto [l, r, i] : scan[i]) {
			if (add[i]) {
				ans[i] += ask(0, 0, SZ, l, r + 1);
			} else {
				add[i] = 1;
				ans[i] -= ask(0, 0, SZ, l, r + 1);
			}
		}
	}

	for (auto c : ans) cout << c << "\n";
	
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'node* ins(node*, std::string, bool)':
selling_rna.cpp:41:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  while (i < s.size()) {
      |         ~~^~~~~~~~~~

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