Submission #434349

#	Time	Username	Problem	Language	Result	Execution time	Memory
434349		hollwo_pelw	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	467 ms	245128 KiB

selling_rna

/* 
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

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

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << endl;
	cout << "Excution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

const int N = 2e6 + 5;

inline int toint(char c){ 
	return (c > 'A') + (c > 'C') + (c > 'G') + (c > 'U');
}

int bit[N];

inline void add(int x, int v) {
	for (++ x; x < N; x += x & -x)
		bit[x] += v;
}

inline int query(int x) {
	int r = 0;
	for (; x; x -= x & -x)
		r += bit[x];
	return r;
}

inline int query(int l, int r) {
	return query(r + 1) - query(l);
}

// x < y && ok

bool comp(const string &x, const string &y, bool ok) {
	for (int i = 0; i < x.size(); i++) {
		if (i == y.size()) return 1;
		if (x[i] > y[i]) return 1;
		if (x[i] < y[i]) return 0;
	}
	return ok;
}

bool comp1(const string &x, const string &y) {
	for (int i = 0; i < x.size(); i++) {
		if (i == y.size()) return 0;
		if (x[i] > y[i]) return 0;
		if (x[i] < y[i]) return 1;
	}
	return 0;
}

int n, q, id[N], pos[N], ans[N];
int adj[N][4], nodecnt;
int tin[N], tout[N], timer;

string a[N], s[N], e[N];

void dfs(int u) {
	tin[u] = ++ timer;
	for (int i = 0; i < 4; i++)
		if (adj[u][i]) dfs(adj[u][i]);
	tout[u] = timer;
}


void Hollwo_Pelw() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++) {
		cin >> s[i] >> e[i], id[i] = i;
	}
	sort(a, a + n);
	sort(id + 1, id + q + 1, [](const int &x, const int &y){
		return pair<string, string>(s[x], e[x]) < pair<string, string>(s[y], e[y]);
	});
	for (int i = 0; i < n; i ++) {
		reverse(a[i].begin(), a[i].end());
		int &p = pos[i];
		for (auto c : a[i]) {
			if (!adj[p][toint(c)])
				adj[p][toint(c)] = ++ nodecnt;
			p = adj[p][toint(c)];
		}
		reverse(a[i].begin(), a[i].end());
	}
	dfs(0);
	int l = 0, r = 1;
	add(tin[pos[0]], 1);
	for (int _ = 1; _ <= q; _++) {
		int i = id[_];
		while (r < n && comp(s[i], a[r], 1)) add(tin[pos[r ++]], +1);
		while (l < r && comp(s[i], a[l], 0)) add(tin[pos[l ++]], -1);
		while (r > l && comp1(s[i], a[r-1])) add(tin[pos[-- r]], -1);

		reverse(e[i].begin(), e[i].end());
		int p = 0, ok = 1;
		for (auto c : e[i]) {
			if (!adj[p][toint(c)]) {
				ok = 0; break;
			}
			p = adj[p][toint(c)];
		}
		ans[i] = (ok ? query(tin[p], tout[p]) : 0);
	}
	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'bool comp(const string&, const string&, bool)':
selling_rna.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < x.size(); i++) {
      |                  ~~^~~~~~~~~~
selling_rna.cpp:72:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if (i == y.size()) return 1;
      |       ~~^~~~~~~~~~~
selling_rna.cpp: In function 'bool comp1(const string&, const string&)':
selling_rna.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < x.size(); i++) {
      |                  ~~^~~~~~~~~~
selling_rna.cpp:81:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   if (i == y.size()) return 0;
      |       ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
selling_rna.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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