Submission #126042

#	Time	Username	Problem	Language	Result	Execution time	Memory
126042		wilwxk	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	221 ms	90004 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+3;
const int MAXS=2e6+3;
int trie[2][MAXS][4];
int v[MAXN][2], pre[2][MAXS], pos[2][MAXS], bit[MAXS+MAXN*2+3];
int respf[MAXN];
vector<pair<int, int> > p;
vector<tuple<int, int, int, int> > qv; 
int n, q, cont[2], contt[2];

int adiciona(string &linha, int k) {
	int cur=0, cara=0;
	for(auto letra : linha) {
		if(letra=='A') cara=0;
		else if(letra=='C') cara=1;
		else if(letra=='G') cara=2;
		else cara=3;
		if(trie[k][cur][cara]==-1) trie[k][cur][cara]=++cont[k];
		cur=trie[k][cur][cara];
		// printf("[%d] %c >> %d // %d\n", k, letra, cara, cur);
	}
	return cur;
}

void dfs(int cur, int k) {
	pre[k][cur]=++contt[k];
	// printf("pre[%d][%d]= %d\n", k, cur, pre[k][cur]);
	for(int i=0; i<4; i++) {
		if(trie[k][cur][i]==-1) continue;
		dfs(trie[k][cur][i], k);
	}
	pos[k][cur]=contt[k];
}

void update(int ind) {
	if(ind<=0) return;
	while(ind<MAXS+MAXN*2) {
		bit[ind]++;
		ind+=ind&-ind;
	}
}
int query(int ind) {
	if(ind<=0) return 0;
	int resp=0;
	while(ind>0) {
		resp+=bit[ind];
		ind-=ind&-ind;
	}
	return resp;
}

int main() {
	scanf("%d %d", &n, &q);
	memset(trie, -1, sizeof(trie));
	for(int i=1; i<=n; i++) {
		char aux[MAXN]; scanf(" %s", aux);
		string cur=aux;
		v[i][0]=adiciona(cur, 0);
		reverse(cur.begin(), cur.end());
		v[i][1]=adiciona(cur, 1);
		// printf("v[%d] >> %d %d\n", i, v[i][0], v[i][1]);
	}

	dfs(0, 0);
	dfs(0, 1);
	for(int i=1; i<=n; i++) p.push_back({pre[0][v[i][0]], pre[1][v[i][1]]});
	sort(p.begin(), p.end());
	// for(auto ponto : p) printf("%d %d\n", ponto.first, ponto.second);


	for(int i=1; i<=q; i++) {
		char aux[MAXN], aux2[MAXN]; scanf(" %s %s", aux, aux2);
		string spre=aux, spos=aux2; reverse(spos.begin(), spos.end());
		int aa=adiciona(spre, 0);
		int bb=adiciona(spos, 1);
		// printf("query %d >> %d %d >> %d %d // %d %d\n", i, aa, bb, pre[0][aa], pos[0][aa], pre[1][bb], pos[1][bb]);
		qv.push_back({pre[0][aa], -i, pre[1][bb], pos[1][bb]}); //x1, ind, y1, y2
		qv.push_back({pos[0][aa], i, pre[1][bb], pos[1][bb]}); //x12, ind, y1, y2
	}
	sort(qv.begin(), qv.end());
	// for(auto cur : qv) { int a, b, c, d, e; tie(a, b, c ,d, e)=cur; printf("%d %d // %d %d // %d\n", a, b, c, d, e); }

	int pont=0;
	for(auto cara : qv) {
		int ini, fim, x, ind; tie(x, ind, ini, fim)=cara;
		// printf("%d %d %d %d // %d\n", x, ind, ini, fim, pont);

		while(pont<p.size()&&p[pont].first<x) update(p[pont++].second);
		if(ind>0) while(pont<p.size()&&p[pont].first<=x) update(p[pont++].second);

		int val=query(fim)-query(ini-1);
		if(ind<0) respf[-ind]-=val;
		else respf[ind]+=val;
	}

	for(int i=1; i<=q; i++) printf("%d\n", respf[i]);
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pont<p.size()&&p[pont].first<x) update(p[pont++].second);
         ~~~~^~~~~~~~~
selling_rna.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ind>0) while(pont<p.size()&&p[pont].first<=x) update(p[pont++].second);
                   ~~~~^~~~~~~~~
selling_rna.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:58:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char aux[MAXN]; scanf(" %s", aux);
                   ~~~~~^~~~~~~~~~~~
selling_rna.cpp:74:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char aux[MAXN], aux2[MAXN]; scanf(" %s %s", aux, aux2);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~

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