oj.uz

Submission #776949

# Submission time Handle Problem Language Result Execution time Memory
776949 2023-07-08T12:16:35 Z TeaTime Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 493 ms 446572 KB 
#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

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

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 446572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15644 KB Output is correct
2 Correct 25 ms 12952 KB Output is correct
3 Correct 30 ms 15028 KB Output is correct
4 Correct 22 ms 13512 KB Output is correct
5 Correct 24 ms 12172 KB Output is correct
6 Correct 30 ms 14480 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Incorrect 493 ms 446572 KB Output isn't correct
9 Halted 0 ms 0 KB -