Submission #552034

#	Time	Username	Problem	Language	Result	Execution time	Memory
552034		Arnch	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1601 ms	574916 KiB

selling_rna

// 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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40