oj.uz

Submission #288836

# Submission time Handle Problem Language Result Execution time Memory
288836 2020-09-02T01:10:01 Z YJU Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 774 ms 827580 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll trie[N][5],sz[N],ti=1,n,m,ans[N],mi[N],ma[N];
string s[N],pre[N],suf[N];
vector<ll> l[N],r[N];

ll to(char c){
	if(c=='A')return 1;
	if(c=='G')return 2;
	if(c=='C')return 3;
	if(c=='U')return 4;
}

void ins(ll id){
	ll j=1;
	REP(i,SZ(s[id])){
		if(!trie[j][to(s[id][i])])trie[j][to(s[id][i])]=++ti;
		mi[j]=(mi[j]?mi[j]:id);
		ma[j]=id;
		++sz[j];
		j=trie[j][to(s[id][i])];
	}
	++sz[j];
	mi[j]=(mi[j]?mi[j]:id);
	ma[j]=id;
}

pll range(string &ts){
	ll j=1;
	REP(i,SZ(ts)){
		if(!trie[j][to(ts[i])])return mp(0,0);
		j=trie[j][to(ts[i])];
	}
	return mp(mi[j],ma[j]);
}

ll ask(string &ts){
	ll j=1;
	REP(i,SZ(ts)){
		if(!trie[j][to(ts[i])])return 0;
		j=trie[j][to(ts[i])];
	}
	return sz[j];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,n)cin>>s[i];
	REP1(i,m)cin>>pre[i]>>suf[i];
	sort(s+1,s+n+1);
	REP1(i,n)ins(i);
	REP1(i,m){
		reverse(suf[i].begin(),suf[i].end());
		pll tmp=range(pre[i]);
		if(tmp.X)l[tmp.X-1].pb(i);
		r[tmp.Y].pb(i);
	}
	memset(sz,0,sizeof(sz));memset(trie,0,sizeof(trie));
	REP1(i,n){
		reverse(s[i].begin(),s[i].end());
		ins(i);
		for(auto j:l[i])ans[j]-=ask(suf[j]);
		for(auto j:r[i])ans[j]+=ask(suf[j]);
	}
	REP1(i,m)cout<<ans[i]<<"\n";
	return 0;
}

Compilation message

selling_rna.cpp: In function 'll to(char)':
selling_rna.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 376056 KB Output is correct
2 Correct 219 ms 376184 KB Output is correct
3 Correct 217 ms 376056 KB Output is correct
4 Correct 217 ms 376056 KB Output is correct
5 Correct 223 ms 376120 KB Output is correct
6 Correct 220 ms 376188 KB Output is correct
7 Correct 224 ms 376184 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 411256 KB Output is correct
2 Correct 309 ms 413560 KB Output is correct
3 Correct 324 ms 414840 KB Output is correct
4 Correct 323 ms 413304 KB Output is correct
5 Runtime error 774 ms 827580 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 377972 KB Output is correct
2 Correct 246 ms 377464 KB Output is correct
3 Correct 250 ms 378100 KB Output is correct
4 Correct 243 ms 377592 KB Output is correct
5 Correct 244 ms 377592 KB Output is correct
6 Correct 255 ms 377884 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 376056 KB Output is correct
2 Correct 219 ms 376184 KB Output is correct
3 Correct 217 ms 376056 KB Output is correct
4 Correct 217 ms 376056 KB Output is correct
5 Correct 223 ms 376120 KB Output is correct
6 Correct 220 ms 376188 KB Output is correct
7 Correct 224 ms 376184 KB Output is correct
8 Correct 302 ms 411256 KB Output is correct
9 Correct 309 ms 413560 KB Output is correct
10 Correct 324 ms 414840 KB Output is correct
11 Correct 323 ms 413304 KB Output is correct
12 Runtime error 774 ms 827580 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -