oj.uz

Submission #126042

# Submission time Handle Problem Language Result Execution time Memory
126042 2019-07-06T20:46:15 Z wilwxk Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 221 ms 90004 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63096 KB Output is correct
2 Correct 55 ms 63096 KB Output is correct
3 Correct 63 ms 63096 KB Output is correct
4 Correct 63 ms 63096 KB Output is correct
5 Correct 54 ms 63096 KB Output is correct
6 Correct 54 ms 63096 KB Output is correct
7 Correct 53 ms 63068 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 89492 KB Output is correct
2 Correct 150 ms 89216 KB Output is correct
3 Correct 152 ms 82732 KB Output is correct
4 Correct 145 ms 82028 KB Output is correct
5 Correct 192 ms 89760 KB Output is correct
6 Correct 221 ms 90004 KB Output is correct
7 Correct 106 ms 68908 KB Output is correct
8 Correct 154 ms 83324 KB Output is correct
9 Correct 147 ms 81176 KB Output is correct
10 Correct 118 ms 78236 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 66488 KB Output is correct
2 Correct 80 ms 65264 KB Output is correct
3 Correct 90 ms 66188 KB Output is correct
4 Correct 84 ms 66064 KB Output is correct
5 Correct 82 ms 65172 KB Output is correct
6 Correct 91 ms 66228 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63096 KB Output is correct
2 Correct 55 ms 63096 KB Output is correct
3 Correct 63 ms 63096 KB Output is correct
4 Correct 63 ms 63096 KB Output is correct
5 Correct 54 ms 63096 KB Output is correct
6 Correct 54 ms 63096 KB Output is correct
7 Correct 53 ms 63068 KB Output is correct
8 Correct 161 ms 89492 KB Output is correct
9 Correct 150 ms 89216 KB Output is correct
10 Correct 152 ms 82732 KB Output is correct
11 Correct 145 ms 82028 KB Output is correct
12 Correct 192 ms 89760 KB Output is correct
13 Correct 221 ms 90004 KB Output is correct
14 Correct 106 ms 68908 KB Output is correct
15 Correct 154 ms 83324 KB Output is correct
16 Correct 147 ms 81176 KB Output is correct
17 Correct 118 ms 78236 KB Output is correct
18 Correct 95 ms 66488 KB Output is correct
19 Correct 80 ms 65264 KB Output is correct
20 Correct 90 ms 66188 KB Output is correct
21 Correct 84 ms 66064 KB Output is correct
22 Correct 82 ms 65172 KB Output is correct
23 Correct 91 ms 66228 KB Output is correct
24 Correct 157 ms 87032 KB Output is correct
25 Correct 177 ms 88252 KB Output is correct
26 Correct 166 ms 86300 KB Output is correct
27 Correct 166 ms 80772 KB Output is correct
28 Correct 201 ms 75620 KB Output is correct
29 Correct 165 ms 72036 KB Output is correct