oj.uz

Submission #434349

# Submission time Handle Problem Language Result Execution time Memory
434349 2021-06-21T03:10:56 Z hollwo_pelw Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 467 ms 245128 KB 
/* 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188332 KB Output is correct
2 Correct 109 ms 188216 KB Output is correct
3 Correct 112 ms 188248 KB Output is correct
4 Correct 111 ms 188236 KB Output is correct
5 Correct 111 ms 188196 KB Output is correct
6 Correct 113 ms 188176 KB Output is correct
7 Correct 114 ms 188248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 245128 KB Output is correct
2 Correct 226 ms 243256 KB Output is correct
3 Correct 171 ms 192820 KB Output is correct
4 Correct 163 ms 192748 KB Output is correct
5 Correct 219 ms 224320 KB Output is correct
6 Correct 203 ms 224860 KB Output is correct
7 Correct 173 ms 194100 KB Output is correct
8 Correct 206 ms 214012 KB Output is correct
9 Correct 194 ms 210924 KB Output is correct
10 Correct 178 ms 207700 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 189156 KB Output is correct
2 Correct 161 ms 188868 KB Output is correct
3 Correct 207 ms 188896 KB Output is correct
4 Correct 173 ms 188740 KB Output is correct
5 Correct 164 ms 188732 KB Output is correct
6 Correct 187 ms 188900 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188332 KB Output is correct
2 Correct 109 ms 188216 KB Output is correct
3 Correct 112 ms 188248 KB Output is correct
4 Correct 111 ms 188236 KB Output is correct
5 Correct 111 ms 188196 KB Output is correct
6 Correct 113 ms 188176 KB Output is correct
7 Correct 114 ms 188248 KB Output is correct
8 Correct 223 ms 245128 KB Output is correct
9 Correct 226 ms 243256 KB Output is correct
10 Correct 171 ms 192820 KB Output is correct
11 Correct 163 ms 192748 KB Output is correct
12 Correct 219 ms 224320 KB Output is correct
13 Correct 203 ms 224860 KB Output is correct
14 Correct 173 ms 194100 KB Output is correct
15 Correct 206 ms 214012 KB Output is correct
16 Correct 194 ms 210924 KB Output is correct
17 Correct 178 ms 207700 KB Output is correct
18 Correct 180 ms 189156 KB Output is correct
19 Correct 161 ms 188868 KB Output is correct
20 Correct 207 ms 188896 KB Output is correct
21 Correct 173 ms 188740 KB Output is correct
22 Correct 164 ms 188732 KB Output is correct
23 Correct 187 ms 188900 KB Output is correct
24 Correct 257 ms 236652 KB Output is correct
25 Correct 324 ms 237264 KB Output is correct
26 Correct 227 ms 235972 KB Output is correct
27 Correct 201 ms 193220 KB Output is correct
28 Correct 467 ms 200816 KB Output is correct
29 Correct 345 ms 189940 KB Output is correct