oj.uz

Submission #392407

# Submission time Handle Problem Language Result Execution time Memory
392407 2021-04-21T04:21:32 Z junodeveloper Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 316 ms 343896 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
using namespace std;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vector<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int INF=1e9;
const int maxsum=2000010;
const int maxm=4;
int trie[maxsum][maxm],sub[maxsum],tcnt;
int L[maxsum],R[maxsum];
vector<int> out[maxsum];
vector<int> ord;
int val(char c) {
	if(c=='A')return 0;
	if(c=='C')return 1;
	if(c=='G')return 2;
	return 3;
}
void add(int i,string& s) {
	int cur=0;
	sub[0]++;
	for(auto& e : s) {
		if(!trie[cur][val(e)])trie[cur][val(e)]=++tcnt;
		cur=trie[cur][val(e)];
		sub[cur]++;
	}
	out[cur].pb(i);
}
void prepare(int cur) {
	for(int i:out[cur]) {
		ord.pb(i);
		L[cur]=min(L[cur],sz(ord)-1);
		R[cur]=max(R[cur],sz(ord)-1);
	}
	for(int i=0;i<4;i++) {
		if(trie[cur][i]) {
			prepare(trie[cur][i]);
			L[cur]=min(L[cur],L[trie[cur][i]]);
			R[cur]=max(R[cur],R[trie[cur][i]]);
		}
	}
}
int n,m;
string S[2000010];
string P[2000010],Q[2000010];
int Pl[2000010],Ql[2000010];
vector<pii> qry[2000010];
int ans[2000010];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,j,k;
	cin>>n>>m;
	for(i=0;i<n;i++) {
		cin>>S[i];
		add(i,S[i]);
	}
	for(i=0;i<=tcnt;i++) {
		L[i]=INF;
		R[i]=0;
	}
	prepare(0);
	for(i=0;i<m;i++) {
		cin>>P[i]>>Q[i];
		reverse(all(Q[i]));
		Pl[i]=P[i].length();
		Ql[i]=Q[i].length();
		int cur=0;
		for(j=0;j<Pl[i];j++) {
			cur=trie[cur][val(P[i][j])];
			if(!cur)break;
		}
		if(!cur)continue;
		if(L[cur]>0)qry[L[cur]-1].pb({i,-1});
		qry[R[cur]].pb({i,1});
	}
	for(i=0;i<=tcnt;i++) {
		sub[i]=0;
		out[i].clear();
		for(j=0;j<4;j++)trie[i][j]=0;
	}
	tcnt=0;
	for(i=0;i<n;i++) {
		reverse(all(S[ord[i]]));
		add(ord[i],S[ord[i]]);
		for(auto& it:qry[i]) {
			int cur=0;
			for(j=0;j<Ql[it.fi];j++) {
				cur=trie[cur][val(Q[it.fi][j])];
				if(!cur)break;
			}
			if(cur)ans[it.fi]+=it.se*sub[cur];
		}
	}
	for(i=0;i<m;i++)cout<<ans[i]<<'\n';
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void _dmp(const char*, TH, TA ...)':
selling_rna.cpp:22:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   22 | while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
      | ^~~~~
selling_rna.cpp:22:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   22 | while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
      |                                ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:10: warning: unused variable 'k' [-Wunused-variable]
   73 |  int i,j,k;
      |          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 282156 KB Output is correct
2 Correct 185 ms 282096 KB Output is correct
3 Correct 170 ms 282164 KB Output is correct
4 Correct 168 ms 282116 KB Output is correct
5 Correct 171 ms 282128 KB Output is correct
6 Correct 164 ms 282168 KB Output is correct
7 Correct 172 ms 282180 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 329388 KB Output is correct
2 Correct 240 ms 327276 KB Output is correct
3 Correct 316 ms 343896 KB Output is correct
4 Correct 300 ms 341272 KB Output is correct
5 Correct 298 ms 321332 KB Output is correct
6 Correct 299 ms 321732 KB Output is correct
7 Correct 212 ms 293724 KB Output is correct
8 Correct 263 ms 314412 KB Output is correct
9 Correct 252 ms 311272 KB Output is correct
10 Correct 232 ms 305668 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 284936 KB Output is correct
2 Correct 186 ms 284100 KB Output is correct
3 Correct 189 ms 284560 KB Output is correct
4 Correct 185 ms 284064 KB Output is correct
5 Correct 186 ms 284084 KB Output is correct
6 Correct 190 ms 284388 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 282156 KB Output is correct
2 Correct 185 ms 282096 KB Output is correct
3 Correct 170 ms 282164 KB Output is correct
4 Correct 168 ms 282116 KB Output is correct
5 Correct 171 ms 282128 KB Output is correct
6 Correct 164 ms 282168 KB Output is correct
7 Correct 172 ms 282180 KB Output is correct
8 Correct 258 ms 329388 KB Output is correct
9 Correct 240 ms 327276 KB Output is correct
10 Correct 316 ms 343896 KB Output is correct
11 Correct 300 ms 341272 KB Output is correct
12 Correct 298 ms 321332 KB Output is correct
13 Correct 299 ms 321732 KB Output is correct
14 Correct 212 ms 293724 KB Output is correct
15 Correct 263 ms 314412 KB Output is correct
16 Correct 252 ms 311272 KB Output is correct
17 Correct 232 ms 305668 KB Output is correct
18 Correct 188 ms 284936 KB Output is correct
19 Correct 186 ms 284100 KB Output is correct
20 Correct 189 ms 284560 KB Output is correct
21 Correct 185 ms 284064 KB Output is correct
22 Correct 186 ms 284084 KB Output is correct
23 Correct 190 ms 284388 KB Output is correct
24 Correct 259 ms 323068 KB Output is correct
25 Correct 266 ms 324728 KB Output is correct
26 Correct 245 ms 322200 KB Output is correct
27 Correct 304 ms 334916 KB Output is correct
28 Correct 280 ms 301172 KB Output is correct
29 Correct 242 ms 290000 KB Output is correct