Submission #112375

# Submission time Handle Problem Language Result Execution time Memory
112375 2019-05-19T07:07:31 Z Mahdi_Jfri Selling RNA Strands (JOI16_selling_rna) C++14
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;
const int maxm = 2e6 + 20;
const int maxs = 5;

vector<pair<int , int> > query[maxn];

string s[maxn] , a[maxn] , b[maxn];

int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];

void add(int ind)
{
	int p = 0;
	for(int ch : s[ind])
	{
		if(!nxt[p][ch])
			nxt[p][ch] = ++id;

		mx[p] = ind;
		sz[p]++;
		p = nxt[p][ch];
	}

	mx[p] = ind;
	sz[p]++;
}

pair<int , int> fn(string s)
{
	int p = 0;
	for(int ch : s)
	{
		if(!nxt[p][ch])
			return make_pair(0 , 0);

		p = nxt[p][ch];
	}

	return {mx[p] , sz[p]};
}

void reval(string &s)
{
	for(auto &ch : s)
	{
		if(ch == 'A')
			ch = 0;
		else if(ch == 'G')
			ch = 1;
		else if(ch == 'C')
			ch = 2;
		else
			ch = 3;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , q;
	cin >> n >> q;

	for(int i = 1; i <= n; i++)
		cin >> s[i];
	sort(s + 1 , s + n + 1);

	for(int i = 1; i <= n; i++)
		add(i);

	for(int i = 0; i < q; i++)
	{
		cin >> a[i] >> b[i];
		reverse(b[i].begin() , b[i].end());

		auto tmp = fn(a[i]);
		int r = tmp.first , l = tmp.first - tmp.second;
		query[r].pb({i , 1});
		query[l].pb({i ,-1});
	}

	memset(nxt , 0 , sizeof nxt);
	memset(mx , 0 , sizeof mx);
	memset(sz , 0 , sizeof sz);
	id = 0;

	for(int i = 1; i <= n; i++)
	{
		reverse(s[i].begin() , s[i].end());
		add(i);

		for(auto tmp : query[i])
			res[tmp.first] += tmp.second * fn(b[tmp.first]).second;
	}

	for(int i = 0; i < q; i++)
		cout << res[i] << endl;
}













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

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;
const int maxm = 2e6 + 20;
const int maxs = 5;

vector<pair<int , int> > query[maxn];

string s[maxn] , a[maxn] , b[maxn];

int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];

void add(int ind)
{
	int p = 0;
	for(int ch : s[ind])
	{
		if(!nxt[p][ch])
			nxt[p][ch] = ++id;

		mx[p] = ind;
		sz[p]++;
		p = nxt[p][ch];
	}

	mx[p] = ind;
	sz[p]++;
}

pair<int , int> fn(string s)
{
	int p = 0;
	for(int ch : s)
	{
		if(!nxt[p][ch])
			return make_pair(0 , 0);

		p = nxt[p][ch];
	}

	return {mx[p] , sz[p]};
}

void reval(string &s)
{
	for(auto &ch : s)
	{
		if(ch == 'A')
			ch = 0;
		else if(ch == 'G')
			ch = 1;
		else if(ch == 'C')
			ch = 2;
		else
			ch = 3;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , q;
	cin >> n >> q;

	for(int i = 1; i <= n; i++)
		cin >> s[i];
	sort(s + 1 , s + n + 1);

	for(int i = 1; i <= n; i++)
		add(i);

	for(int i = 0; i < q; i++)
	{
		cin >> a[i] >> b[i];
		reverse(b[i].begin() , b[i].end());

		auto tmp = fn(a[i]);
		int r = tmp.first , l = tmp.first - tmp.second;
		query[r].pb({i , 1});
		query[l].pb({i ,-1});
	}

	memset(nxt , 0 , sizeof nxt);
	memset(mx , 0 , sizeof mx);
	memset(sz , 0 , sizeof sz);
	id = 0;

	for(int i = 1; i <= n; i++)
	{
		reverse(s[i].begin() , s[i].end());
		add(i);

		for(auto tmp : query[i])
			res[tmp.first] += tmp.second * fn(b[tmp.first]).second;
	}

	for(int i = 0; i < q; i++)
		cout << res[i] << endl;
}













Compilation message

selling_rna.cpp:126:11: error: redefinition of 'const int maxn'
 const int maxn = 1e5 + 20;
           ^~~~
selling_rna.cpp:7:11: note: 'const int maxn' previously defined here
 const int maxn = 1e5 + 20;
           ^~~~
selling_rna.cpp:127:11: error: redefinition of 'const int maxm'
 const int maxm = 2e6 + 20;
           ^~~~
selling_rna.cpp:8:11: note: 'const int maxm' previously defined here
 const int maxm = 2e6 + 20;
           ^~~~
selling_rna.cpp:128:11: error: redefinition of 'const int maxs'
 const int maxs = 5;
           ^~~~
selling_rna.cpp:9:11: note: 'const int maxs' previously defined here
 const int maxs = 5;
           ^~~~
selling_rna.cpp:130:36: error: redefinition of 'std::vector<std::pair<int, int> > query [100020]'
 vector<pair<int , int> > query[maxn];
                                    ^
selling_rna.cpp:11:26: note: 'std::vector<std::pair<int, int> > query [100020]' previously declared here
 vector<pair<int , int> > query[maxn];
                          ^~~~~
selling_rna.cpp:132:14: error: redefinition of 'std::__cxx11::string s [100020]'
 string s[maxn] , a[maxn] , b[maxn];
              ^
selling_rna.cpp:13:8: note: 'std::__cxx11::string s [100020]' previously declared here
 string s[maxn] , a[maxn] , b[maxn];
        ^
selling_rna.cpp:132:24: error: redefinition of 'std::__cxx11::string a [100020]'
 string s[maxn] , a[maxn] , b[maxn];
                        ^
selling_rna.cpp:13:18: note: 'std::__cxx11::string a [100020]' previously declared here
 string s[maxn] , a[maxn] , b[maxn];
                  ^
selling_rna.cpp:132:34: error: redefinition of 'std::__cxx11::string b [100020]'
 string s[maxn] , a[maxn] , b[maxn];
                                  ^
selling_rna.cpp:13:28: note: 'std::__cxx11::string b [100020]' previously declared here
 string s[maxn] , a[maxn] , b[maxn];
                            ^
selling_rna.cpp:134:19: error: redefinition of 'int nxt [2000020][5]'
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                   ^
selling_rna.cpp:15:5: note: 'int nxt [2000020][5]' previously declared here
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
     ^~~
selling_rna.cpp:134:30: error: redefinition of 'int mx [2000020]'
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                              ^
selling_rna.cpp:15:23: note: 'int mx [2000020]' previously declared here
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                       ^~
selling_rna.cpp:134:41: error: redefinition of 'int sz [2000020]'
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                         ^
selling_rna.cpp:15:34: note: 'int sz [2000020]' previously declared here
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                  ^~
selling_rna.cpp:134:45: error: redefinition of 'int id'
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                             ^~
selling_rna.cpp:15:45: note: 'int id' previously declared here
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                             ^~
selling_rna.cpp:134:58: error: redefinition of 'int res [100020]'
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                                          ^
selling_rna.cpp:15:50: note: 'int res [100020]' previously declared here
 int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id , res[maxn];
                                                  ^~~
selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:136:6: error: redefinition of 'void add(int)'
 void add(int ind)
      ^~~
selling_rna.cpp:17:6: note: 'void add(int)' previously defined here
 void add(int ind)
      ^~~
selling_rna.cpp: In function 'std::pair<int, int> fn(std::__cxx11::string)':
selling_rna.cpp:153:17: error: redefinition of 'std::pair<int, int> fn(std::__cxx11::string)'
 pair<int , int> fn(string s)
                 ^~
selling_rna.cpp:34:17: note: 'std::pair<int, int> fn(std::__cxx11::string)' previously defined here
 pair<int , int> fn(string s)
                 ^~
selling_rna.cpp: In function 'void reval(std::__cxx11::string&)':
selling_rna.cpp:167:6: error: redefinition of 'void reval(std::__cxx11::string&)'
 void reval(string &s)
      ^~~~~
selling_rna.cpp:48:6: note: 'void reval(std::__cxx11::string&)' previously defined here
 void reval(string &s)
      ^~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:182:5: error: redefinition of 'int main()'
 int main()
     ^~~~
selling_rna.cpp:63:5: note: 'int main()' previously defined here
 int main()
     ^~~~