oj.uz

Submission #320739

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

typedef 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 = 2e6 + 10;
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("%d%d", &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("%d\n", get2(t, X.F, X.S));
	}
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117736 KB Output is correct
2 Correct 72 ms 117732 KB Output is correct
3 Correct 82 ms 117732 KB Output is correct
4 Correct 74 ms 117732 KB Output is correct
5 Correct 72 ms 117732 KB Output is correct
6 Correct 72 ms 117732 KB Output is correct
7 Correct 72 ms 117864 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 415464 KB Output is correct
2 Correct 515 ms 401892 KB Output is correct
3 Correct 416 ms 371556 KB Output is correct
4 Correct 421 ms 359780 KB Output is correct
5 Correct 490 ms 450656 KB Output is correct
6 Correct 480 ms 455524 KB Output is correct
7 Correct 276 ms 134224 KB Output is correct
8 Correct 535 ms 324708 KB Output is correct
9 Correct 481 ms 293092 KB Output is correct
10 Correct 374 ms 286308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 119392 KB Output is correct
2 Correct 181 ms 119524 KB Output is correct
3 Correct 210 ms 119520 KB Output is correct
4 Correct 189 ms 119008 KB Output is correct
5 Correct 180 ms 119524 KB Output is correct
6 Correct 215 ms 119604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117736 KB Output is correct
2 Correct 72 ms 117732 KB Output is correct
3 Correct 82 ms 117732 KB Output is correct
4 Correct 74 ms 117732 KB Output is correct
5 Correct 72 ms 117732 KB Output is correct
6 Correct 72 ms 117732 KB Output is correct
7 Correct 72 ms 117864 KB Output is correct
8 Correct 518 ms 415464 KB Output is correct
9 Correct 515 ms 401892 KB Output is correct
10 Correct 416 ms 371556 KB Output is correct
11 Correct 421 ms 359780 KB Output is correct
12 Correct 490 ms 450656 KB Output is correct
13 Correct 480 ms 455524 KB Output is correct
14 Correct 276 ms 134224 KB Output is correct
15 Correct 535 ms 324708 KB Output is correct
16 Correct 481 ms 293092 KB Output is correct
17 Correct 374 ms 286308 KB Output is correct
18 Correct 236 ms 119392 KB Output is correct
19 Correct 181 ms 119524 KB Output is correct
20 Correct 210 ms 119520 KB Output is correct
21 Correct 189 ms 119008 KB Output is correct
22 Correct 180 ms 119524 KB Output is correct
23 Correct 215 ms 119604 KB Output is correct
24 Correct 554 ms 364004 KB Output is correct
25 Correct 649 ms 364136 KB Output is correct
26 Correct 532 ms 361188 KB Output is correct
27 Correct 442 ms 327684 KB Output is correct
28 Correct 644 ms 165596 KB Output is correct
29 Correct 496 ms 126676 KB Output is correct