oj.uz

Submission #245905

# Submission time Handle Problem Language Result Execution time Memory
245905 2020-07-07T17:57:52 Z Goolakh Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 133 ms 46456 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][4],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) cnt[v=C[v][c-'a']=(!C[v][c-'a'] ? ++nn:C[v][c-'a'])]++;
	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(int i:{0,1,2,3})if(C[v][i]) dfs(C[v][i]);
	ft[v]=tt;
}
map<char,char> num;
void mkay(string &s){for(auto &c:s) c=num[c];}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	num['A']='a', num['C']='b', num['G']='c', num['U']='d';
	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
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 46456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 21608 KB Output is correct
2 Correct 86 ms 21108 KB Output is correct
3 Correct 112 ms 21728 KB Output is correct
4 Correct 88 ms 20980 KB Output is correct
5 Correct 86 ms 20856 KB Output is correct
6 Correct 113 ms 21348 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18432 KB Output is correct
2 Correct 14 ms 18432 KB Output is correct
3 Correct 16 ms 18432 KB Output is correct
4 Correct 15 ms 18432 KB Output is correct
5 Correct 15 ms 18432 KB Output is correct
6 Correct 14 ms 18432 KB Output is correct
7 Correct 15 ms 18432 KB Output is correct
8 Runtime error 114 ms 46456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -