oj.uz

Submission #1042231

# Submission time Handle Problem Language Result Execution time Memory
1042231 2024-08-02T17:02:04 Z milo_milkshake Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 125 ms 148560 KB 
#include <bits/stdc++.h>
using namespace std;
#define uwu "RNA"

typedef long long ll;
#define pb push_back
#define endl '\n'
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
const int N = 1e5 + 3;
const int M = 2e6 + 2;
const int INF = 1e9 + 7;

int n, q;

string s[N];
int id[N];

int pre[M][4];
pair<int,int> range[N];
int nodepre = 1;

int suf[M][4];
vector <int> vt[M];
int nodesuf = 1;

int num(char c){
	if (c == 'U') return 3;
	if (c == 'G') return 1;
	return c - 'A';
}
void addpre(string s, int inc){
	int pos = 1, len = s.size();
	FOR(i, 0, len - 1){
		int c = num(s[i]); 
		if (!pre[pos][c]){
			pre[pos][c] = ++nodepre;
			range[nodepre].first = INF;
		}

		pos = pre[pos][c];  
		range[pos].first = min(range[pos].first, inc);
		range[pos].second = max(range[pos].second, inc);
	}
}
void addsuf(string s, int inc){
	int pos = 1, len = s.size();
	FORD(i, len - 1, 0){
		int c = num(s[i]);
		if (!suf[pos][c]) suf[pos][c] = ++nodesuf;
		pos = suf[pos][c]; vt[pos].pb(inc);
	}
}
pair<int,int> findpre(string s){
	int pos = 1, len = s.size();
	FOR(i, 0, len - 1){
		int c = num(s[i]); pos = pre[pos][c];  
		if (pos == 0) break;
	}
	return range[pos]; 
}
int calc(string s, pair<int,int> inc){
	int pos = 1, len = s.size();
	FORD(i, len - 1, 0){
		int c = num(s[i]); pos = suf[pos][c];
		if (pos == 0) break; 
	}

	int L = lower_bound(vt[pos].begin(), vt[pos].end(), inc.first) - vt[pos].begin();
	int R = upper_bound(vt[pos].begin(), vt[pos].end(), inc.second) - vt[pos].begin();
	return R - L;
}
void solve(void){
	FOR(i, 1, n) id[i] = i;
	sort(id + 1, id + n + 1, [&] (int u, int v){
		return s[u] < s[v];
	});

	FOR(i, 1, n){
		addpre(s[id[i]], i);
		addsuf(s[id[i]], i);
	}

	while(q--){
		string P, S; cin >> P >> S;
		cout << calc(S, findpre(P)) << endl;
	}
}
signed main(){
 	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if(fopen(uwu".inp","r")){
		freopen(uwu".inp","r",stdin);
		freopen(uwu".out","w",stdout);
	}

	cin >> n >> q;
	FOR(i, 1, n) cin >> s[i];

	solve();

	cerr << "\nTime used: " << clock() << "ms\n";
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen(uwu".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   freopen(uwu".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 148560 KB Output is correct
2 Correct 122 ms 145860 KB Output is correct
3 Incorrect 44 ms 72016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53200 KB Output is correct
2 Correct 30 ms 53496 KB Output is correct
3 Correct 31 ms 53588 KB Output is correct
4 Correct 26 ms 53360 KB Output is correct
5 Correct 30 ms 53360 KB Output is correct
6 Correct 34 ms 53584 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 52312 KB Output is correct
2 Correct 14 ms 52312 KB Output is correct
3 Correct 16 ms 52316 KB Output is correct
4 Correct 14 ms 52316 KB Output is correct
5 Correct 12 ms 52316 KB Output is correct
6 Correct 17 ms 52312 KB Output is correct
7 Correct 14 ms 52316 KB Output is correct
8 Correct 125 ms 148560 KB Output is correct
9 Correct 122 ms 145860 KB Output is correct
10 Incorrect 44 ms 72016 KB Output isn't correct
11 Halted 0 ms 0 KB -