oj.uz

Submission #552034

# Submission time Handle Problem Language Result Execution time Memory
552034 2022-04-22T09:05:26 Z Arnch Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 574916 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 2e6 + 10, mod = 1e9 + 7, A = 30;

void addtrie(string x, int pos);

int n, m, sz, nxt[N][A], nxt2[N][A], ans[N], cnt[N], sz2;
string s[N], t[N][2];
vector<int> ind[N], ind2[N];

inline void get_input() {
	cin >>n >>m;
	for(int i = 0; i < n; i++) {
		cin >>s[i];
		addtrie(s[i], i);
	}
	for(int i = 0; i < m; i++) cin >>t[i][0] >>t[i][1];
}

inline void addtrie(string x, int pos) {
	int p = 0;
	for(int i = 0; i < Sz(x); i++) {
		if(nxt[p][x[i] - 'A']) p = nxt[p][x[i] - 'A'];
		else p = nxt[p][x[i] - 'A'] = ++sz;
	}
	p = 0;
	for(int i = Sz(x) - 1; i >= 0; i--) {
		if(nxt2[p][x[i] - 'A']) p = nxt2[p][x[i] - 'A'];
		else p = nxt2[p][x[i] - 'A'] = ++sz2;
	}
}

inline void dojob(int x) {
	int p = 0;
	for(int i = 0; i < Sz(t[x][0]); i++) {
		if(!nxt[p][t[x][0][i] - 'A']) return;
		p = nxt[p][t[x][0][i] - 'A'];
	}
	ind[p].push_back(x);
	p = 0;
	for(int i = Sz(t[x][1]) - 1; i >= 0; i--) {
		if(!nxt2[p][t[x][1][i] - 'A']) return;
		p = nxt2[p][t[x][1][i] - 'A'];
	}
	ind2[p].push_back(x);
}


inline void call(int pos) {
	int p = 0;
	for(int i = 0; i < Sz(s[pos]); i++) {
		p = nxt[p][s[pos][i] - 'A'];
		for(auto j : ind[p]) {
			cnt[j]++;
		}
	}
	p = 0;
	for(int i = Sz(s[pos]) - 1; i >= 0; i--) {
		p = nxt2[p][s[pos][i] - 'A'];
		for(auto j : ind2[p]) {
			cnt[j]++;
			if(cnt[j] == 2) ans[j]++;
		}
	}
	p = 0;
	for(int i = 0; i < Sz(s[pos]); i++) {
		p = nxt[p][s[pos][i] - 'A'];
		for(auto j : ind[p]) {
			cnt[j]--;
		}
	}
	p = 0;
	for(int i = Sz(s[pos]) - 1; i >= 0; i--) {
		p = nxt2[p][s[pos][i] - 'A'];
		for(auto j : ind2[p]) {
			cnt[j]--;
		}
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	get_input();

	for(int i = 0; i < m; i++) {
		dojob(i);
	}

	for(int i = 0; i < n; i++) {
		call(i);
	}

	for(int i = 0; i < m; i++) {
		cout<<ans[i] <<endl;
	}


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 282140 KB Output is correct
2 Correct 134 ms 282136 KB Output is correct
3 Correct 123 ms 282064 KB Output is correct
4 Correct 125 ms 282156 KB Output is correct
5 Correct 137 ms 282160 KB Output is correct
6 Correct 153 ms 282064 KB Output is correct
7 Correct 125 ms 282160 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 517796 KB Output is correct
2 Correct 441 ms 505360 KB Output is correct
3 Correct 489 ms 514404 KB Output is correct
4 Correct 449 ms 503360 KB Output is correct
5 Correct 401 ms 570708 KB Output is correct
6 Correct 382 ms 574916 KB Output is correct
7 Correct 316 ms 288416 KB Output is correct
8 Correct 383 ms 456108 KB Output is correct
9 Correct 346 ms 428992 KB Output is correct
10 Correct 540 ms 422224 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1601 ms 282988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 282140 KB Output is correct
2 Correct 134 ms 282136 KB Output is correct
3 Correct 123 ms 282064 KB Output is correct
4 Correct 125 ms 282156 KB Output is correct
5 Correct 137 ms 282160 KB Output is correct
6 Correct 153 ms 282064 KB Output is correct
7 Correct 125 ms 282160 KB Output is correct
8 Correct 394 ms 517796 KB Output is correct
9 Correct 441 ms 505360 KB Output is correct
10 Correct 489 ms 514404 KB Output is correct
11 Correct 449 ms 503360 KB Output is correct
12 Correct 401 ms 570708 KB Output is correct
13 Correct 382 ms 574916 KB Output is correct
14 Correct 316 ms 288416 KB Output is correct
15 Correct 383 ms 456108 KB Output is correct
16 Correct 346 ms 428992 KB Output is correct
17 Correct 540 ms 422224 KB Output is correct
18 Execution timed out 1601 ms 282988 KB Time limit exceeded
19 Halted 0 ms 0 KB -