oj.uz

Submission #552033

# Submission time Handle Problem Language Result Execution time Memory
552033 2022-04-22T09:03:12 Z Arnch Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 575276 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];

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];
}

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;
	}
}

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);
}


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]) {
//			wtf(pos), wtf(j);
			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]) {
//			wtf(pos), wtf(j);
			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 124 ms 282060 KB Output is correct
2 Correct 132 ms 282168 KB Output is correct
3 Correct 132 ms 282160 KB Output is correct
4 Correct 125 ms 282148 KB Output is correct
5 Correct 130 ms 282072 KB Output is correct
6 Correct 133 ms 282188 KB Output is correct
7 Correct 132 ms 282184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 519084 KB Output is correct
2 Correct 448 ms 505616 KB Output is correct
3 Correct 458 ms 514764 KB Output is correct
4 Correct 470 ms 503616 KB Output is correct
5 Correct 385 ms 571040 KB Output is correct
6 Correct 378 ms 575276 KB Output is correct
7 Correct 286 ms 288696 KB Output is correct
8 Correct 353 ms 456324 KB Output is correct
9 Correct 349 ms 429260 KB Output is correct
10 Correct 621 ms 422516 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 282060 KB Output is correct
2 Correct 132 ms 282168 KB Output is correct
3 Correct 132 ms 282160 KB Output is correct
4 Correct 125 ms 282148 KB Output is correct
5 Correct 130 ms 282072 KB Output is correct
6 Correct 133 ms 282188 KB Output is correct
7 Correct 132 ms 282184 KB Output is correct
8 Correct 391 ms 519084 KB Output is correct
9 Correct 448 ms 505616 KB Output is correct
10 Correct 458 ms 514764 KB Output is correct
11 Correct 470 ms 503616 KB Output is correct
12 Correct 385 ms 571040 KB Output is correct
13 Correct 378 ms 575276 KB Output is correct
14 Correct 286 ms 288696 KB Output is correct
15 Correct 353 ms 456324 KB Output is correct
16 Correct 349 ms 429260 KB Output is correct
17 Correct 621 ms 422516 KB Output is correct
18 Execution timed out 1584 ms 283392 KB Time limit exceeded
19 Halted 0 ms 0 KB -