Submission #51155

#	Time	Username	Problem	Language	Result	Execution time	Memory
51155		shoemakerjo	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	472 ms	105360 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;
#define maxn 100010
#define maxd 3000010
#define pii pair<int, int>
#define insert trieadd
#define mp make_pair

//might need to double hash but whatever
const bool debug = false;
int N, M;
int BIT[maxn];
int ans[maxn]; //for printing b/c we do not compute in order
vector<pair< pair<string, string>, int>> cust; //customers
vector<vector<int>> activate(maxn); //indices of original guys
vector<vector<int>> deactivate(maxn);
vector<string> ostr;
int enc[27];
int endcust[maxn];
int endostr[maxn];

int trie[maxd][4]; //store indices
int tcind[maxd];
int numnodes = 1; //start at node 1

void insert(string cur, int ind) {
	++ind;
	int tmp = 1;
	for (int i = 0; i < cur.length(); i++) {
		int nx = enc[cur[i]-'A'];
		if (trie[tmp][nx]) {
			tmp = trie[tmp][nx];
			continue;
		}
		trie[tmp][nx] = ++numnodes;
		tmp = numnodes;
	}
	if (tcind[tmp] == 0) tcind[tmp] = ind;
}

vector<int> matches;

void qt(string cur) {
	int tmp = 1;
	for (int i = 0; i < cur.length(); i++) {
		int nx = enc[cur[i]-'A'];
		if (!trie[tmp][nx]) return;
		tmp = trie[tmp][nx];
		if (tcind[tmp]) matches.push_back(tcind[tmp]-1);
	}
}

int qu(int spot) {
	int ans = 0;
	while (spot > 0) {
		ans += BIT[spot];
		spot -= spot & (-spot);
	}
	return ans;
}

int query(int lo, int hi) {
	++hi;
	++lo;
	return qu(hi) - qu(lo-1);
}

void up(int ind, int diff) {
	while (ind < maxn) {
		BIT[ind] += diff;
		ind += ind & (-ind);
	}
}

void update(int ind, int diff) {
	++ind;
	up(ind, diff);
}

int main() {
	enc['A'-'A'] = 0;
	enc['C'-'A'] = 1;
	enc['G'-'A'] = 2;
	enc['U'-'A'] = 3;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	string cur;

	for (int i = 0; i < N; i++) {
		cin >> cur;
		string rev = "" + cur;
		reverse(rev.begin(), rev.end());
		ostr.push_back(rev);
	}
	sort(ostr.begin(), ostr.end()); //should be fast enough
	string pref, suf;
	for (int i = 0; i < M; i++) {
		cin >> pref >> suf;
		cust.push_back(mp(mp(pref, suf), i));
	}
	sort(cust.begin(), cust.end()); //should be fast enough

	if (debug) {
	cout << endl;
	cout << "asdfgfahafdsdvadfbashbasf OSTR" << endl;
	for (int i = 0; i < ostr.size(); i++) {
		cout << ostr[i] << endl;
	}
	cout << endl;

	cout << endl;
	for (int i = 0; i < cust.size(); i++) {
		cout << cust[i].first.first << " " << 
			cust[i].first.second <<
			 " " << cust[i].second << endl;
	}
	cout << endl;
	}
	
	vector<string> cp; //customer prefixes
	for (int i = 0; i < M; i++) {
		cp.push_back(cust[i].first.first);
	}

	endcust[cp.size()-1] = cp.size()-1;
	for (int i = cp.size()-2; i >= 0; i--) {
		if (cp[i] == cp[i+1]) {
			endcust[i] = endcust[i+1];
		}
		else endcust[i] = i;
	}

	endostr[ostr.size()-1] = ostr.size()-1;
	for (int i = ostr.size()-2; i >= 0; i--) {
		if (ostr[i] == ostr[i+1]) {
			endostr[i] = endostr[i+1];
		}
		else endostr[i] = i;
	}

	for (int i = 0; i < cp.size(); i++) {
		insert(cp[i], i);
	}

	for (int i = 0; i < ostr.size(); i++) {

		string rev = "" + ostr[i];
		reverse(rev.begin(), rev.end());

		matches.clear();
		qt(rev); //find all the prefix matches for this
		if (debug) cout << rev << " matches:" << endl;
		for (int val : matches) {
			activate[val].push_back(i);
			deactivate[endcust[val]+1].push_back(i);
			if (debug) 
				cout << "       " << val << " " << endcust[val] << endl; 
		}
	}

	//clear out the trie b/c why not
	numnodes = 1;
	for (int i = 0; i < maxd; i++) {
		trie[i][0] = trie[i][1] = trie[i][2] = trie[i][3] = 0;
		tcind[i] = 0;
	}

	// for (int i = 0; i < ostr.size(); i++) {
	// 	insert(ostr[i], i);
	// }

	if (debug) cout << endl << "----------------" << endl << endl;

	//looping through the M strings
	for (int i = 0; i < M; i++) {
		// cout << "i:   " << i << endl;
		for (int val : activate[i]) {
			// cout << "    adding in " << val << endl;
			update(val, 1);
		}
		for (int val : deactivate[i]) {
			// cout << "    taking out " << val << endl;
			update(val, -1);
		}
		int indo = cust[i].second;
		string suf = cust[i].first.second;
		//don't care at all about the prefix
		string rev = "" + suf;
		reverse(rev.begin(), rev.end());
		
		//then do my queries
		// matches.clear();
		// qt(rev);

		//maybe i want binary serach for this half
		int lo = 0;
		int hi = ostr.size()-1;
		int rl = rev.length();
		while (lo < hi) {
			int mid = (lo+hi)/2;

			if (ostr[mid].length() < rl) {
				if (rev < ostr[mid]) {
					hi = mid;
				}
				else lo = mid+1;
				continue;
			}

			if (rev > ostr[mid].substr(0, rl)) {
				lo = mid+1;
			}
			else {
				hi = mid;
			}
		}
		int qs = lo;
		if (ostr[qs].length() < rev.length() || 
			ostr[qs].substr(0, rev.length()) != rev) {
			if (debug) cout << rev << " DOES NOT MATCH" << endl;
			continue; //no match
		}		
		lo = 0;
		hi = ostr.size()-1;
		while (lo < hi) {
			int mid = (lo+hi+1)/2;

			if (ostr[mid].length() < rl) {
				if (rev < ostr[mid]) {
					hi = mid-1;
				}
				else lo = mid;
				continue;
			}

			if (rev < ostr[mid].substr(0, rl)) {
				hi = mid-1;
			}
			else {
				lo = mid;
			}
		}
		// cout << rev << " matches from " << lo << " to " << hi << endl;
		int qe = lo;
		if (debug) cout << rev << " matches from " << qs << " to " << qe << endl;
		ans[indo] = query(qs, qe);

		
	}
	for (int i = 0; i < M; i++) {
		cout << ans[i] << '\n';
	}
	cout.flush();
	cin >> N;



}
//don't think we actually need a hash, we can just bin search 

Compilation message (stderr)

selling_rna.cpp: In function 'void trieadd(std::__cxx11::string, int)':
selling_rna.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.length(); i++) {
                  ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void qt(std::__cxx11::string)':
selling_rna.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.length(); i++) {
                  ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ostr.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cust.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cp.size(); i++) {
                  ~~^~~~~~~~~~~
selling_rna.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ostr.size(); i++) {
                  ~~^~~~~~~~~~~~~
selling_rna.cpp:204:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ostr[mid].length() < rl) {
        ~~~~~~~~~~~~~~~~~~~^~~~
selling_rna.cpp:230:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ostr[mid].length() < rl) {
        ~~~~~~~~~~~~~~~~~~~^~~~

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