oj.uz

Submission #245558

# Submission time Handle Problem Language Result Execution time Memory
245558 2020-07-06T18:17:57 Z ruler Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 113 ms 87072 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e5 + 2, M = 2e6 + 2, SGM = 4;

int t, clk, CNT[N], C[M][SGM], ST[N], FN[N], Z[N], ANS[N];
string S[N], SUF[N];
vector<pii> Q[N], T;

int Add(string &s) {
	int now = 0;
	for (char c : s) {
		if (!C[now][c - 'A']) C[now][c - 'A'] = ++t;
		now = C[now][c - 'A'];
		CNT[now]++;
	}
	return now;
}
void Compress(string &s) {
	for (char &c : s) {
		if (c == 'G') c = 'B';
		if (c == 'U') c = 'D';
	}
}
void DFS(int v) {
	ST[v] = clk++;
	for (int i = 0; i < SGM; i++) if (C[v][i]) DFS(C[v][i]);
	FN[v] = clk;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> S[i]; Compress(S[i]);
		Z[i] = Add(S[i]);
	}
	DFS(0);
	for (int i = 0; i < n; i++) T.push_back(make_pair(ST[Z[i]], i));
	sort(all(T));
	for (int i = 0; i < q; i++) {
		string pre; cin >> pre >> SUF[i]; Compress(pre), Compress(SUF[i]);
		int now = 0;
		for (char c : pre) {
			now = C[now][c - 'A'];
			if (!now) break;
		}
		if (now == 0) continue;
		reverse(all(SUF[i]));
		int r = lower_bound(all(T), make_pair(ST[now], 0)) - T.begin();
		int l = lower_bound(all(T), make_pair(FN[now], 0)) - T.begin();
		Q[r].push_back(make_pair(-1, i));
		Q[l].push_back(make_pair(+1, i));
	}
	memset(C, 0, sizeof C), memset(CNT, 0, sizeof CNT), t = 0;
	for (int i = 0; i < n; i++) reverse(all(S[i]));
	for (int i = 0; i <= n; i++) {
		for (pii p : Q[i]) {
			int now = 0;
			for (char c : SUF[p.second]) {
				now = C[now][c - 'A'];
				if (!now) break;
			}
			if (now == 0) continue;
			ANS[p.second] += p.first * CNT[now];
		}
		if (i < n) Add(S[T[i].second]);
	}
	for (int i = 0; i < q; i++) cout << ANS[i] << endl;
	

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 87072 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 55 ms 43380 KB Output is correct
2 Correct 46 ms 42232 KB Output is correct
3 Correct 58 ms 42612 KB Output is correct
4 Correct 51 ms 42228 KB Output is correct
5 Correct 54 ms 41976 KB Output is correct
6 Correct 53 ms 42228 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 40704 KB Output is correct
2 Correct 26 ms 40704 KB Output is correct
3 Correct 27 ms 40704 KB Output is correct
4 Correct 26 ms 40704 KB Output is correct
5 Correct 26 ms 40704 KB Output is correct
6 Correct 29 ms 40704 KB Output is correct
7 Correct 26 ms 40704 KB Output is correct
8 Runtime error 113 ms 87072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -