oj.uz

Submission #56835

# Submission time Handle Problem Language Result Execution time Memory
56835 2018-07-12T19:41:13 Z Mamnoon_Siam Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1166 ms 58724 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

int n, m;
vector<string> ok, rev;
vector<int> v;

vector<int> t[100005 * 4];

void build(int u, int b, int e, vector<int> &vec) {
	for(int i = b; i <= e; i++) t[u].push_back(vec[i]);
	sort(all(t[u]));
	if(b == e) return;
	int mid = b + e >> 1;
	build(u << 1, b, mid, vec);
	build(u << 1 | 1, mid + 1, e, vec);
}
int query(int u, int b, int e, int i, int j, int l, int r) {
	if(b > j or e < i) return 0;
	if(i <= b and e <= j) return upper_bound(all(t[u]), r) - lower_bound(all(t[u]), l);
	int mid = b + e >> 1;
	return query(u << 1, b, mid, i, j, l, r) + query(u << 1 | 1, mid + 1, e, i, j, l, r);
}
int query(int i, int j, int l, int r) {
	if(i > j or l > r) return 0;
	return query(1, 0, n - 1, i, j, l, r);
}

bool IsPrefix(string &s, string &pre) {
	if(pre.size() > s.size()) return false;
	for(int i = 0; i < pre.size(); i++) {
		if(pre[i] != s[i]) return false;
	} return true;
}

int32_t main () {
	// freopen("in", "r", stdin);
	cin >> n >> m;
	ok.resize(n), rev.resize(n);
	for(string &b : ok) cin >> b;
	sort(all(ok));
	for(int i = 0; i < n; i++) {
		rev[i] = ok[i];
		reverse(all(rev[i]));
		v.push_back(i);
	}
	sort(all(v), [](int x, int y){return rev[x] < rev[y];});
	sort(all(rev));

	build(1, 0, n - 1, v);

	// for(int i = 0; i < n; i++) cout << ok[i] << ' '; cout << endl;
	// for(int i = 0; i < n; i++) cout << rev[i] << ' '; cout << endl;
	// for(int i = 0; i < n; i++) cout << v[i] << ' '; cout << endl;

	while(m--) {
		int lo, hi;
		string pre, suf;
		cin >> pre >> suf;
		reverse(all(suf));
		int l = lower_bound(all(ok), pre) - ok.begin(), r;
		if(l >= ok.size() or !IsPrefix(ok[l], pre)) r = l - 1;
		else {
			lo = l, hi = ok.size() - 1;
			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(IsPrefix(ok[mid], pre)) {
					lo = mid + 1;
					r = mid;
				} else {
					hi = mid - 1;
				}
			}
		}
		int lit = lower_bound(all(rev), suf) - rev.begin(), rit;
		if(lit >= ok.size() or !IsPrefix(rev[lit], suf)) rit = lit - 1;
		else {
			lo = lit, hi = rev.size() - 1;
			while(lo <= hi) {
				int mid = lo + hi >> 1;
				if(IsPrefix(rev[mid], suf)) {
					lo = mid + 1;
					rit = mid;
				} else {
					hi = mid - 1;
				}
			}
		}
		// cout << "l = " << l << ", r = " << r << ", lit = " << lit << ", rit = " << rit << endl;
		cout << query(lit, rit, l, r) << endl;
	}
}

Compilation message

selling_rna.cpp: In function 'int myrand(int, int)':
selling_rna.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
selling_rna.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
selling_rna.cpp: In function 'void build(int, int, int, std::vector<int>&)':
selling_rna.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~
selling_rna.cpp: In function 'int query(int, int, int, int, int, int, int)':
selling_rna.cpp:48:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~
selling_rna.cpp: In function 'bool IsPrefix(std::__cxx11::string&, std::__cxx11::string&)':
selling_rna.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pre.size(); i++) {
                 ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:89:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(l >= ok.size() or !IsPrefix(ok[l], pre)) r = l - 1;
      ~~^~~~~~~~~~~~
selling_rna.cpp:93:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:103:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lit >= ok.size() or !IsPrefix(rev[lit], suf)) rit = lit - 1;
      ~~~~^~~~~~~~~~~~
selling_rna.cpp:107:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:53:38: warning: 'rit' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return query(1, 0, n - 1, i, j, l, r);
                                      ^
selling_rna.cpp:102:55: note: 'rit' was declared here
   int lit = lower_bound(all(rev), suf) - rev.begin(), rit;
                                                       ^~~
selling_rna.cpp:53:38: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return query(1, 0, n - 1, i, j, l, r);
                                      ^
selling_rna.cpp:88:51: note: 'r' was declared here
   int l = lower_bound(all(ok), pre) - ok.begin(), r;
                                                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 8 ms 9828 KB Output is correct
3 Correct 11 ms 9904 KB Output is correct
4 Correct 8 ms 9904 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 8 ms 9904 KB Output is correct
7 Correct 9 ms 9904 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 15148 KB Output is correct
2 Correct 338 ms 15760 KB Output is correct
3 Correct 249 ms 15760 KB Output is correct
4 Correct 237 ms 15844 KB Output is correct
5 Correct 173 ms 15844 KB Output is correct
6 Correct 171 ms 15844 KB Output is correct
7 Correct 302 ms 15844 KB Output is correct
8 Correct 371 ms 15844 KB Output is correct
9 Correct 351 ms 15844 KB Output is correct
10 Correct 227 ms 15844 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 19992 KB Output is correct
2 Correct 216 ms 19992 KB Output is correct
3 Correct 295 ms 19992 KB Output is correct
4 Correct 183 ms 19992 KB Output is correct
5 Correct 183 ms 19992 KB Output is correct
6 Correct 288 ms 20520 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 8 ms 9828 KB Output is correct
3 Correct 11 ms 9904 KB Output is correct
4 Correct 8 ms 9904 KB Output is correct
5 Correct 9 ms 9904 KB Output is correct
6 Correct 8 ms 9904 KB Output is correct
7 Correct 9 ms 9904 KB Output is correct
8 Correct 207 ms 15148 KB Output is correct
9 Correct 338 ms 15760 KB Output is correct
10 Correct 249 ms 15760 KB Output is correct
11 Correct 237 ms 15844 KB Output is correct
12 Correct 173 ms 15844 KB Output is correct
13 Correct 171 ms 15844 KB Output is correct
14 Correct 302 ms 15844 KB Output is correct
15 Correct 371 ms 15844 KB Output is correct
16 Correct 351 ms 15844 KB Output is correct
17 Correct 227 ms 15844 KB Output is correct
18 Correct 246 ms 19992 KB Output is correct
19 Correct 216 ms 19992 KB Output is correct
20 Correct 295 ms 19992 KB Output is correct
21 Correct 183 ms 19992 KB Output is correct
22 Correct 183 ms 19992 KB Output is correct
23 Correct 288 ms 20520 KB Output is correct
24 Correct 294 ms 23032 KB Output is correct
25 Correct 481 ms 27348 KB Output is correct
26 Correct 324 ms 31088 KB Output is correct
27 Correct 390 ms 35220 KB Output is correct
28 Correct 1166 ms 58724 KB Output is correct
29 Correct 811 ms 58724 KB Output is correct