oj.uz

Submission #56836

# Submission time Handle Problem Language Result Execution time Memory
56836 2018-07-12T19:44:08 Z Mamnoon_Siam Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1081 ms 36116 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;

namespace mst {
	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));

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

	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 << mst::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 mst::build(int, int, int, std::vector<int>&)':
selling_rna.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = b + e >> 1;
             ~~^~~
selling_rna.cpp: In function 'int mst::query(int, int, int, int, int, int, int)':
selling_rna.cpp:49:15: 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:60: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:87: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:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:101: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:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = lo + hi >> 1;
               ~~~^~~~
selling_rna.cpp:54:39: warning: 'rit' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return query(1, 0, n - 1, i, j, l, r);
                                       ^
selling_rna.cpp:100:55: note: 'rit' was declared here
   int lit = lower_bound(all(rev), suf) - rev.begin(), rit;
                                                       ^~~
selling_rna.cpp:54:39: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return query(1, 0, n - 1, i, j, l, r);
                                       ^
selling_rna.cpp:86: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 13 ms 9720 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 15 ms 9892 KB Output is correct
4 Correct 11 ms 9892 KB Output is correct
5 Correct 14 ms 9892 KB Output is correct
6 Correct 12 ms 9988 KB Output is correct
7 Correct 12 ms 9988 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 15176 KB Output is correct
2 Correct 246 ms 15900 KB Output is correct
3 Correct 265 ms 15900 KB Output is correct
4 Correct 246 ms 16000 KB Output is correct
5 Correct 169 ms 16000 KB Output is correct
6 Correct 160 ms 16000 KB Output is correct
7 Correct 304 ms 16000 KB Output is correct
8 Correct 419 ms 16000 KB Output is correct
9 Correct 347 ms 16000 KB Output is correct
10 Correct 282 ms 16000 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 20136 KB Output is correct
2 Correct 175 ms 20136 KB Output is correct
3 Correct 209 ms 20136 KB Output is correct
4 Correct 160 ms 20136 KB Output is correct
5 Correct 174 ms 20136 KB Output is correct
6 Correct 275 ms 20136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9720 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 15 ms 9892 KB Output is correct
4 Correct 11 ms 9892 KB Output is correct
5 Correct 14 ms 9892 KB Output is correct
6 Correct 12 ms 9988 KB Output is correct
7 Correct 12 ms 9988 KB Output is correct
8 Correct 223 ms 15176 KB Output is correct
9 Correct 246 ms 15900 KB Output is correct
10 Correct 265 ms 15900 KB Output is correct
11 Correct 246 ms 16000 KB Output is correct
12 Correct 169 ms 16000 KB Output is correct
13 Correct 160 ms 16000 KB Output is correct
14 Correct 304 ms 16000 KB Output is correct
15 Correct 419 ms 16000 KB Output is correct
16 Correct 347 ms 16000 KB Output is correct
17 Correct 282 ms 16000 KB Output is correct
18 Correct 241 ms 20136 KB Output is correct
19 Correct 175 ms 20136 KB Output is correct
20 Correct 209 ms 20136 KB Output is correct
21 Correct 160 ms 20136 KB Output is correct
22 Correct 174 ms 20136 KB Output is correct
23 Correct 275 ms 20136 KB Output is correct
24 Correct 326 ms 20136 KB Output is correct
25 Correct 466 ms 20136 KB Output is correct
26 Correct 301 ms 20136 KB Output is correct
27 Correct 396 ms 20136 KB Output is correct
28 Correct 1081 ms 36116 KB Output is correct
29 Correct 772 ms 36116 KB Output is correct