oj.uz

답안 #245900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245900 2020-07-07T17:47:04 Z Goolakh Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 128 ms 47096 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,q,C[maxn][2],nn,tt,wat[maxn],st[maxn],ft[maxn],cnt[maxn],ans[maxn];
vector<ll> qq[maxn];
vector<pll> Q[maxn];
string s[maxn],pre[maxn],suf[maxn];

ll add(string s){
	ll v=0;
	for(auto c:s) v=C[v][c-'a']=(!C[v][c-'a'] ? ++nn:C[v][c-'a']), cnt[v]++;
	return v;
}
ll dff(string s){
	ll v=0;
	for(auto c:s){
		v=C[v][c-'a'];
		if(v==0) break;
	}
	return v;
}
void dfs(ll v=0){
	wat[st[v]=tt++]=v;
	for(bool i:{0,1})if(C[v][i]) dfs(C[v][i]);
	ft[v]=tt;
}
void mkay(string &s){for(auto &c:s) c=(c=='G' || c=='B' ? 'a':'b');}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>s[i]; mkay(s[i]);
		qq[add(s[i])].pb(i);
		reverse(all(s[i]));
	}
	dfs();
	for(int i=0;i<q;i++){
		cin>>pre[i]>>suf[i]; mkay(pre[i]), mkay(suf[i]);
		ll v=dff(pre[i]);
		if(v){
			Q[st[v]].pb({-1,i});
			Q[ft[v]].pb({+1,i});
			reverse(all(suf[i]));
		}
	}
	memset(C,0,sizeof(C)), memset(cnt,0,sizeof(cnt)), nn=0;
	for(int i=0;i<=tt;i++){
		for(auto x:Q[i]){
			ll v=dff(suf[x.S]);
			if(v) ans[x.S]+=x.F*cnt[v];
		}
		for(auto x:qq[wat[i]]) add(s[x]);
	}
	for(int i=0;i<q;i++) cout<<ans[i]<<endl;
 	
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 16896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 75 ms 47096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 128 ms 20844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 16896 KB Output isn't correct
2 Halted 0 ms 0 KB -