oj.uz

Submission #788696

# Submission time Handle Problem Language Result Execution time Memory
788696 2023-07-20T13:36:52 Z Dan4Life Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 485 ms 607400 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)1e5+10;
const int mxS = (int)2e6+10;
vector<int> xd[mxS];
int trie[2][4][mxS];
int L[mxS], R[mxS];
int n, m, node=2;
string s[mxS];

void add(string &s, int ind, int t){
	int v = 1;
	for(auto u : s){
		int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
		if(!trie[t][c][v]) trie[t][c][v]=node++;
		v = trie[t][c][v];
		if(!t){
			if(!L[v]) L[v]=ind;
			R[v]=max(R[v],ind);
		}
		else xd[v].pb(ind);
	}
}

int get(string &s, int t){
	int v = 1;
	for(auto u : s){
		int c = (u=='A'?0:u=='C'?1:u=='G'?2:3);
		v = trie[t][c][v]; if(!v) return 0;
	}
	return v;
}

int32_t main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
	for(int i = 0; i < n; i++)
		add(s[i],i+1,0),reverse(all(s[i])),add(s[i],i+1,1);
	for(int i = 0; i < m; i++){
		string s, t; cin >> s >> t; reverse(all(t));
		int ind = get(s,0), ind2=get(t,1);
		int l = L[ind], r=R[ind];
		if(!l or !ind or !ind2) { cout << "0\n"; continue; }
		int pos1 = lower_bound(all(xd[ind2]),l)-begin(xd[ind2]);
		int pos2 = upper_bound(all(xd[ind2]),r)-begin(xd[ind2])-1;
		cout << max(0ll, pos2-pos1+1) << "\n";
	}
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |  ^~~
selling_rna.cpp:40:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |                                          ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 109956 KB Output is correct
2 Correct 45 ms 109912 KB Output is correct
3 Correct 46 ms 109984 KB Output is correct
4 Correct 47 ms 109900 KB Output is correct
5 Correct 46 ms 109980 KB Output is correct
6 Correct 48 ms 109888 KB Output is correct
7 Correct 46 ms 109936 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 259076 KB Output is correct
2 Correct 293 ms 267580 KB Output is correct
3 Correct 195 ms 233200 KB Output is correct
4 Correct 232 ms 231276 KB Output is correct
5 Runtime error 485 ms 607400 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 111276 KB Output is correct
2 Correct 125 ms 111788 KB Output is correct
3 Correct 123 ms 111588 KB Output is correct
4 Correct 104 ms 111240 KB Output is correct
5 Correct 104 ms 111548 KB Output is correct
6 Correct 119 ms 111472 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 109956 KB Output is correct
2 Correct 45 ms 109912 KB Output is correct
3 Correct 46 ms 109984 KB Output is correct
4 Correct 47 ms 109900 KB Output is correct
5 Correct 46 ms 109980 KB Output is correct
6 Correct 48 ms 109888 KB Output is correct
7 Correct 46 ms 109936 KB Output is correct
8 Correct 312 ms 259076 KB Output is correct
9 Correct 293 ms 267580 KB Output is correct
10 Correct 195 ms 233200 KB Output is correct
11 Correct 232 ms 231276 KB Output is correct
12 Runtime error 485 ms 607400 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -