oj.uz

Submission #320735

# Submission time Handle Problem Language Result Execution time Memory
320735 2020-11-09T16:22:27 Z parsabahrami Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 266 ms 209540 KB 
//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
    	if (b & 1) ans = ans * a % md;
    return ans;
}
const ll MAXN = 3e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll nxt[2][MAXN][30], L[MAXN], R[MAXN], n, q, id[2] = {1, 1};
vector<ll> vec[MAXN]; string C[MAXN];

void update1(string x, ll p) {
	ll v = 0;
	for (ll i = 0; i < sz(x); i++) {
		if (nxt[0][v][x[i] - 'A'] == 0) nxt[0][v][x[i] - 'A'] = id[0]++;
		L[v] = min(L[v], p);
		R[v] = max(R[v], p);
		v = nxt[0][v][x[i] - 'A'];
	}
	L[v] = min(L[v], p);
	R[v] = max(R[v], p);
}

void update2(string x, ll p) {
	ll v = 0;
	for (ll i = sz(x) - 1; ~i; i--) {
		if (nxt[1][v][x[i] - 'A'] == 0) nxt[1][v][x[i] - 'A'] = id[1]++;
		vec[v].push_back(p);
		v = nxt[1][v][x[i] - 'A'];
	}
	vec[v].push_back(p);
}

pll get1(string x) {
	ll v = 0;
	for (ll i = 0; i < sz(x); i++) {
		if (nxt[0][v][x[i] - 'A'] == 0) return {-1, -1};
		v = nxt[0][v][x[i] - 'A'];
	}
	return {L[v], R[v]};
}

ll get2(string x, ll l, ll r) {
	if (r == -1 || l == -1) return 0;
	ll v = 0;
	for (ll i = sz(x) - 1; ~i; i--) {
		if (nxt[1][v][x[i] - 'A'] == 0) return 15;
		v = nxt[1][v][x[i] - 'A'];
	}
	return upper_bound(all(vec[v]), r) - lower_bound(all(vec[v]), l);
}

int main() {
	fill(L, L + MAXN, MOD);
	scanf("%lld%lld", &n, &q);
	for (ll i = 1; i <= n; i++) {
		cin >> C[i];
	}
	sort(C + 1, C + n + 1);
	for (ll i = 1; i <= n; i++) {
		update1(C[i], i);
		update2(C[i], i);
	}
	while (q--) {
		string s, t;
		cin >> s >> t;
		pll X = get1(s);
		printf("%lld\n", get2(t, X.F, X.S));
	}
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 209540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 21464 KB Output is correct
2 Correct 118 ms 22244 KB Output is correct
3 Correct 158 ms 21852 KB Output is correct
4 Correct 127 ms 21096 KB Output is correct
5 Correct 119 ms 22112 KB Output is correct
6 Correct 168 ms 21872 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19180 KB Output is correct
2 Correct 15 ms 19180 KB Output is correct
3 Correct 14 ms 19180 KB Output is correct
4 Correct 14 ms 19180 KB Output is correct
5 Correct 16 ms 19180 KB Output is correct
6 Correct 14 ms 19180 KB Output is correct
7 Correct 14 ms 19180 KB Output is correct
8 Runtime error 266 ms 209540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -