제출 #528841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528841		Koosha_mv	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	300 ms	431272 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e6+99,S=4;

int n,m,ans[N],L[N],R[N],fenwik[N];
string s[N],t[N],a[N],b[N];
vector<int> vec[N];
vector<pair<int,int>> Q[N];

void add(int x, int val=1){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; }
int get(int x) { int res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }

int g(char c){
	if(c=='A') return 0;
	if(c=='U') return 1;
	if(c=='G') return 2;
	if(c=='C') return 3;
}
struct trie{
	int cnt,Time,st[N],ft[N],child[N][S];
	trie(){
		Time=cnt=1;
		f(i,0,N) f(j,0,S) child[i][j]=0;
	}
	void add(string s){
		int now=1;
		f(i,0,s.size()){
			int nxt=g(s[i]);
			if(!child[now][nxt]) child[now][nxt]=++cnt;
			now=child[now][nxt];
			//eror(now);
		}
	}
	void dfs(int u=1){
		st[u]=Time++;
		f(i,0,S) if(child[u][i]) dfs(child[u][i]);
		ft[u]=Time;
	}
	pair<int,int> find(string s){
		int now=1;
		f(i,0,s.size()){
			int nxt=g(s[i]);
			if(!child[now][nxt]) return {st[now],ft[now]};
			now=child[now][nxt];
		}
		return {st[now],ft[now]};
	}
} t1,t2;

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	f(i,0,n) cin>>s[i],t[i]=s[i],reverse(all(t[i]));
	f(i,0,m){
		cin>>a[i]>>b[i];
		reverse(all(b[i]));
		t1.add(a[i]);
		t2.add(b[i]);
	}
	t1.dfs();
	t2.dfs();
	f(i,0,n){
		vec[t1.find(s[i]).F].pb(t2.find(t[i]).F);
		//cout<<t1.find(s[i]).F<<" - "<<t2.find(t[i]).F<<endl;
	}
	f(i,0,m){
		pair<int,int> e1=t1.find(a[i]),e2=t2.find(b[i]);
		e1.F--,e1.S--;
		e2.F--,e2.S--;
		//erorp(e1);
		//erorp(e2);
		L[i]=e2.F;
		R[i]=e2.S;
		Q[e1.F].pb({i,-1});
		Q[e1.S].pb({i,+1});
	}
	f(i,0,N){
		for(auto x : vec[i]) add(x);
		for(auto p : Q[i]){
			int res=get(R[p.F])-get(L[p.F]);
			ans[p.F]+=res*p.S;
		}
	}
	f(i,0,m) cout<<ans[i]<<" ";
}
/*
2 1
GCGCUACCCCAACACAAGGCAAGAUAUA
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCGCUACCC A


GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

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

selling_rna.cpp: In member function 'void trie::add(std::string)':
selling_rna.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   47 |   f(i,0,s.size()){
      |     ~~~~~~~~~~~~               
selling_rna.cpp:47:3: note: in expansion of macro 'f'
   47 |   f(i,0,s.size()){
      |   ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::find(std::string)':
selling_rna.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   61 |   f(i,0,s.size()){
      |     ~~~~~~~~~~~~               
selling_rna.cpp:61:3: note: in expansion of macro 'f'
   61 |   f(i,0,s.size()){
      |   ^
selling_rna.cpp: In function 'int g(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40