oj.uz

Submission #776952

# Submission time Handle Problem Language Result Execution time Memory
776952 2023-07-08T12:18:06 Z TeaTime Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 647 ms 661608 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 = 2'000'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 53 ms 94320 KB Output is correct
2 Correct 47 ms 94340 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 51 ms 94324 KB Output is correct
5 Correct 46 ms 94388 KB Output is correct
6 Correct 47 ms 94292 KB Output is correct
7 Correct 47 ms 94340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 548692 KB Output is correct
2 Correct 515 ms 536160 KB Output is correct
3 Correct 489 ms 529272 KB Output is correct
4 Correct 475 ms 508484 KB Output is correct
5 Correct 639 ms 653300 KB Output is correct
6 Correct 647 ms 661608 KB Output is correct
7 Correct 100 ms 106984 KB Output is correct
8 Correct 455 ms 431768 KB Output is correct
9 Correct 401 ms 379244 KB Output is correct
10 Correct 352 ms 366276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 104504 KB Output is correct
2 Correct 74 ms 101804 KB Output is correct
3 Correct 81 ms 103868 KB Output is correct
4 Correct 68 ms 102300 KB Output is correct
5 Correct 71 ms 101188 KB Output is correct
6 Correct 77 ms 103264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94320 KB Output is correct
2 Correct 47 ms 94340 KB Output is correct
3 Correct 48 ms 94288 KB Output is correct
4 Correct 51 ms 94324 KB Output is correct
5 Correct 46 ms 94388 KB Output is correct
6 Correct 47 ms 94292 KB Output is correct
7 Correct 47 ms 94340 KB Output is correct
8 Correct 510 ms 548692 KB Output is correct
9 Correct 515 ms 536160 KB Output is correct
10 Correct 489 ms 529272 KB Output is correct
11 Correct 475 ms 508484 KB Output is correct
12 Correct 639 ms 653300 KB Output is correct
13 Correct 647 ms 661608 KB Output is correct
14 Correct 100 ms 106984 KB Output is correct
15 Correct 455 ms 431768 KB Output is correct
16 Correct 401 ms 379244 KB Output is correct
17 Correct 352 ms 366276 KB Output is correct
18 Correct 77 ms 104504 KB Output is correct
19 Correct 74 ms 101804 KB Output is correct
20 Correct 81 ms 103868 KB Output is correct
21 Correct 68 ms 102300 KB Output is correct
22 Correct 71 ms 101188 KB Output is correct
23 Correct 77 ms 103264 KB Output is correct
24 Correct 471 ms 483220 KB Output is correct
25 Correct 491 ms 487884 KB Output is correct
26 Correct 496 ms 477052 KB Output is correct
27 Correct 468 ms 453936 KB Output is correct
28 Correct 257 ms 172236 KB Output is correct
29 Correct 119 ms 116252 KB Output is correct