oj.uz

Submission #288840

# Submission time Handle Problem Language Result Execution time Memory
288840 2020-09-02T01:12:06 Z YJU Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 565 ms 795976 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=4e6+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;
	return 0;
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 751864 KB Output is correct
2 Correct 439 ms 751864 KB Output is correct
3 Correct 429 ms 751992 KB Output is correct
4 Correct 434 ms 751864 KB Output is correct
5 Correct 428 ms 752120 KB Output is correct
6 Correct 440 ms 751796 KB Output is correct
7 Correct 441 ms 751864 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 787064 KB Output is correct
2 Correct 521 ms 789240 KB Output is correct
3 Correct 551 ms 790472 KB Output is correct
4 Correct 544 ms 788984 KB Output is correct
5 Correct 530 ms 795512 KB Output is correct
6 Correct 538 ms 795976 KB Output is correct
7 Correct 474 ms 763256 KB Output is correct
8 Correct 543 ms 786420 KB Output is correct
9 Correct 514 ms 782840 KB Output is correct
10 Correct 488 ms 777276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 753652 KB Output is correct
2 Correct 452 ms 753144 KB Output is correct
3 Correct 466 ms 753396 KB Output is correct
4 Correct 452 ms 752888 KB Output is correct
5 Correct 449 ms 752980 KB Output is correct
6 Correct 450 ms 753272 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 751864 KB Output is correct
2 Correct 439 ms 751864 KB Output is correct
3 Correct 429 ms 751992 KB Output is correct
4 Correct 434 ms 751864 KB Output is correct
5 Correct 428 ms 752120 KB Output is correct
6 Correct 440 ms 751796 KB Output is correct
7 Correct 441 ms 751864 KB Output is correct
8 Correct 518 ms 787064 KB Output is correct
9 Correct 521 ms 789240 KB Output is correct
10 Correct 551 ms 790472 KB Output is correct
11 Correct 544 ms 788984 KB Output is correct
12 Correct 530 ms 795512 KB Output is correct
13 Correct 538 ms 795976 KB Output is correct
14 Correct 474 ms 763256 KB Output is correct
15 Correct 543 ms 786420 KB Output is correct
16 Correct 514 ms 782840 KB Output is correct
17 Correct 488 ms 777276 KB Output is correct
18 Correct 455 ms 753652 KB Output is correct
19 Correct 452 ms 753144 KB Output is correct
20 Correct 466 ms 753396 KB Output is correct
21 Correct 452 ms 752888 KB Output is correct
22 Correct 449 ms 752980 KB Output is correct
23 Correct 450 ms 753272 KB Output is correct
24 Correct 524 ms 786296 KB Output is correct
25 Correct 530 ms 787704 KB Output is correct
26 Correct 519 ms 785344 KB Output is correct
27 Correct 540 ms 785832 KB Output is correct
28 Correct 565 ms 768632 KB Output is correct
29 Correct 509 ms 758356 KB Output is correct