제출 #392407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392407		junodeveloper	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	316 ms	343896 KiB

selling_rna

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40