oj.uz

Submission #391109

# Submission time Handle Problem Language Result Execution time Memory
391109 2021-04-17T21:18:17 Z Return_0 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 267 ms 192464 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

#define ask(l, r, x) ll(upper_bound(All(x), r) - lower_bound(All(x), l))

cl N = 1e5 + 7, K = 2e6 + 7;

ll tin [K], tout [K], chr [26], n, q;
string s [N], t1, t2;

ll tr [K][4], lst, tr2 [K][4], lst2;
vector <ll> id [K], id2 [K];

inline void add2 (const string &_s, cl &_id) {
	ll cur = 0;
	for (auto &ch : _s) {
		id2[cur].push_back(_id);
		if (!tr2[cur][chr[ch - 'A']]) tr2[cur][chr[ch - 'A']] = ++lst2;
		cur = tr2[cur][chr[ch - 'A']];
	}
	id2[cur].push_back(_id);
}

inline void add (const string &_s, cl &_id) {
	ll cur = 0;
	for (auto &ch : _s) {
		if (!tr[cur][chr[ch - 'A']]) tr[cur][chr[ch - 'A']] = ++lst;
		cur = tr[cur][chr[ch - 'A']];
	}
	id[cur].push_back(_id);
}

void _sort (cl &v = 0) {
	tin[v] = lst + 1;
	for (auto &x : id[v]) add2(s[x], ++lst);
	if (tr[v][0]) _sort(tr[v][0]);
	if (tr[v][1]) _sort(tr[v][1]);
	if (tr[v][2]) _sort(tr[v][2]);
	if (tr[v][3]) _sort(tr[v][3]);
	tout[v] = lst;
}

ll get_id (const string &_s) {
	ll cur = 0;
	for (auto &ch : _s) {
		if (!tr[cur][chr[ch - 'A']]) return -1;
		cur = tr[cur][chr[ch - 'A']];
	}
	return cur;
}

ll get_id2 (const string &_s) {
	ll cur = 0;
	for (auto &ch : _s) {
		if (!tr2[cur][chr[ch - 'A']]) return -1;
		cur = tr2[cur][chr[ch - 'A']];
	}
	return cur;
}

ll solve () {
	cin>> t1 >> t2;
	ll x = get_id(t1);
	if (!~x) return 0;
	reverse(All(t2));
	ll y = get_id2(t2);
	if (!~y) return 0;
	return max(0, ask(tin[x], tout[x], id2[y]));
}

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

	chr['A' - 'A'] = 0, chr['C' - 'A'] = 1, chr['G' - 'A'] = 2, chr['U' - 'A'] = 3;
	cin>> n >> q;
	for (ll i = 1; i <= n; i++) {
		cin>> s[i];
		add(s[i], i);
		reverse(All(s[i]));
	}

	lst = 0; _sort();
	for (; q--;) cout<< solve() << '\n';

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
2 4
AUGC
AGC
G C
AU C
A C
C C

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 97348 KB Output is correct
2 Correct 55 ms 97352 KB Output is correct
3 Correct 56 ms 97432 KB Output is correct
4 Correct 55 ms 97308 KB Output is correct
5 Correct 57 ms 97364 KB Output is correct
6 Correct 56 ms 97376 KB Output is correct
7 Correct 57 ms 97340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 192464 KB Output is correct
2 Correct 237 ms 191304 KB Output is correct
3 Correct 212 ms 160300 KB Output is correct
4 Correct 210 ms 158104 KB Output is correct
5 Correct 244 ms 187204 KB Output is correct
6 Correct 249 ms 188472 KB Output is correct
7 Correct 122 ms 113152 KB Output is correct
8 Correct 251 ms 161648 KB Output is correct
9 Correct 217 ms 153196 KB Output is correct
10 Correct 195 ms 149744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 98872 KB Output is correct
2 Correct 76 ms 98780 KB Output is correct
3 Correct 79 ms 98956 KB Output is correct
4 Correct 73 ms 98820 KB Output is correct
5 Correct 77 ms 98788 KB Output is correct
6 Correct 85 ms 98856 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 97348 KB Output is correct
2 Correct 55 ms 97352 KB Output is correct
3 Correct 56 ms 97432 KB Output is correct
4 Correct 55 ms 97308 KB Output is correct
5 Correct 57 ms 97364 KB Output is correct
6 Correct 56 ms 97376 KB Output is correct
7 Correct 57 ms 97340 KB Output is correct
8 Correct 238 ms 192464 KB Output is correct
9 Correct 237 ms 191304 KB Output is correct
10 Correct 212 ms 160300 KB Output is correct
11 Correct 210 ms 158104 KB Output is correct
12 Correct 244 ms 187204 KB Output is correct
13 Correct 249 ms 188472 KB Output is correct
14 Correct 122 ms 113152 KB Output is correct
15 Correct 251 ms 161648 KB Output is correct
16 Correct 217 ms 153196 KB Output is correct
17 Correct 195 ms 149744 KB Output is correct
18 Correct 85 ms 98872 KB Output is correct
19 Correct 76 ms 98780 KB Output is correct
20 Correct 79 ms 98956 KB Output is correct
21 Correct 73 ms 98820 KB Output is correct
22 Correct 77 ms 98788 KB Output is correct
23 Correct 85 ms 98856 KB Output is correct
24 Correct 259 ms 179568 KB Output is correct
25 Correct 267 ms 179956 KB Output is correct
26 Correct 247 ms 178588 KB Output is correct
27 Correct 222 ms 151364 KB Output is correct
28 Correct 218 ms 123864 KB Output is correct
29 Correct 134 ms 106796 KB Output is correct