제출 #255614

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

selling_rna

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=2e6+6;

int n,m;
int trie[3],timer[3];
int G[2*N],ANS[N],T[2*N][5][3],in[N][3],out[N][3];

string u,q;

pair < int , int > d[2*N];
vector < pair < bool ,  int > > v[2*N][3];

inline int C(char c) {
	if (c=='A') return 0;
	if (c=='C') return 1;
	if (c=='G') return 2;
	return 3;
}

pair < int , int > idx;
void Upd(int id,int x,bool ty) { 
	if (u.size()==x) {
		v[id][ty].pb(idx);
		return ;
	}
	int t=C(u[x]); 
	if (!T[id][t][ty]) T[id][t][ty]=++trie[ty];
	Upd(T[id][t][ty],x+1,ty);
}

void Dfs(int x,int ty) {
	++timer[ty];
	for (int i=0; i<v[x][ty].size(); i++) {
		int type=v[x][ty][i].F,idx=v[x][ty][i].S;
		if (!type) {
			if (!ty) 
				d[idx].F=timer[ty];
					else 
				d[idx].S=timer[ty];
		}
			else in[idx][ty]=timer[ty];		
	}
	
	for (int i=0; i<4; i++) 
		if (T[x][i][ty])
			Dfs(T[x][i][ty],ty);
	
	for (int i=0; i<v[x][ty].size(); i++) {
		int type=v[x][ty][i].F,idx=v[x][ty][i].S;
		if (type) out[idx][ty]=timer[ty];	
	}		
}

void Up(int x) {
	while (x<=2*N-5) {
		G[x]++;
		x+=(x & -x);
	}
}

int Get(int x) {
	int res=0;
	while (x>0) {
		res+=G[x];
		x-=(x & -x);
	}
	return res;
}

main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n>>m;
	for (int i=1; i<=n; i++) {
		cin>>u;
		idx={0,i};
		Upd(0,0,0);
		reverse(u.begin(),u.end());
		Upd(0,0,1);
	}
		
	for (int i=1; i<=m; i++) {
		cin>>u>>q;
		idx={1,i};
		Upd(0,0,0);
		reverse(q.begin(),q.end()); u=q;
		Upd(0,0,1);
	}

	Dfs(0,0);
	Dfs(0,1);

	vector < pair < int , pair < int , int > > > Q;
	
	for (int i=1; i<=m; i++) {
		Q.pb({in[i][0]-1,{-1,i}});
		Q.pb({out[i][0],{1,i}});
	}
	
	sort(d+1,d+n+1);
	sort(Q.begin(),Q.end());
	
	int j=0;
	for (int i=0; i<Q.size(); i++) {
		int qy=Q[i].F,dl=Q[i].S.F,id=Q[i].S.S;
		
		while (j+1<=n && d[j+1].F<=qy) {
			++j;
			Up(d[j].S);	
		}
		
		ANS[id]+=dl*(Get(out[id][1])-Get(in[id][1]-1));
	}
	
	for (int i=1; i<=m; i++)
		cout<<ANS[i]<<"\n";
}

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

selling_rna.cpp: In function 'void Upd(int, int, bool)':
selling_rna.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (u.size()==x) {
      ~~~~~~~~^~~
selling_rna.cpp: In function 'void Dfs(int, int)':
selling_rna.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x][ty].size(); i++) {
                ~^~~~~~~~~~~~~~~~
selling_rna.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x][ty].size(); i++) {
                ~^~~~~~~~~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:74:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<Q.size(); i++) {
                ~^~~~~~~~~

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