oj.uz

Submission #291959

# Submission time Handle Problem Language Result Execution time Memory
291959 2020-09-06T05:43:25 Z eggag32 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 592 ms 194428 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
#define ll int
const int mxN = 1e5 + 5;
const int MOD = 12277039;
const int MOD2 = 112111211;
 
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

struct HASH{
	size_t operator () (const pair<int, int> &x) const {
		return hash<long long>()(((long long)(x.first)) ^ (((long long)(x.second)) << 32));
	}
};

int n, m;
string s[mxN];
pair<pair<string, string>, int> p[mxN];
gp_hash_table<pi, int, HASH> hshs;
vector<pair<ll, ll>> haS[mxN];
vector<pair<ll, ll>> haS1[mxN];
vector<pair<ll, ll>> haP[mxN];
pair<ll, ll> h[mxN];
 
bool cmp(pair<pair<string, string>, int> a, pair<pair<string, string>, int> b){
	return a.fi.fi < b.fi.fi;
}
 
void add(int ind){
	//adds all the suffix hashes of s[ind]
	rep(i, s[ind].size()) hshs[haS1[ind][i]]++;
}

void del(int ind){
	//deletes all the suffix hashes of s[ind]
	rep(i, s[ind].size()) hshs[haS1[ind][i]]--;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n >> m;
	rep(i, n) cin >> s[i];
	sort(s, s + n);
	rep(i, n){
		ll hsh = 1LL, hsh1 = 1LL;
		for(int j = 1; j <= (int)s[i].size(); j++){
			hsh = (hsh * 31) + (ll)(s[i][j - 1] - 'a') + 1;
			hsh1 = (hsh1 * 37) + (ll)(s[i][j - 1] - 'a') + 1;
			hsh %= MOD;
			hsh1 %= MOD2;
			haS[i].pb(mp(hsh, hsh1));
		}
	}
	rep(i, n){
		ll hsh = 1LL, hsh1 = 1LL;
		for(int j = (int)s[i].size(); j >= 1; j--){
			hsh = (hsh * 31) + (ll)(s[i][j - 1] - 'a') + 1;
			hsh1 = (hsh1 * 37) + (ll)(s[i][j - 1] - 'a') + 1;
			hsh %= MOD;
			hsh1 %= MOD2;
			haS1[i].pb(mp(hsh, hsh1));
		}
	}
	rep(i, m){
		cin >> p[i].fi.fi >> p[i].fi.se;
		p[i].se = i;
	}
	sort(p, p + m, cmp);
	rep(i, m){
		ll hsh = 1LL, hsh1 = 1LL;
		for(int j = (int)p[i].fi.se.size(); j >= 1; j--){
			hsh = (hsh * 31) + (ll)(p[i].fi.se[j - 1] - 'a') + 1;
			hsh1 = (hsh1 * 37) + (ll)(p[i].fi.se[j - 1] - 'a') + 1;
			hsh %= MOD;
			hsh1 %= MOD2;
		}
		h[i] = mp(hsh, hsh1);
	}
	rep(i, m){
		ll hsh = 1LL, hsh1 = 1LL;
		for(int j = 1; j <= (int)p[i].fi.fi.size(); j++){
			hsh = (hsh * 31) + (ll)(p[i].fi.fi[j - 1] - 'a') + 1;
			hsh1 = (hsh1 * 37) + (ll)(p[i].fi.fi[j - 1] - 'a') + 1;
			hsh %= MOD;
			hsh1 %= MOD2;
			haP[i].pb(mp(hsh, hsh1));
		}
	}
	vi ext(m, 0), ans(m, 0);
	repn(i, 1, m){
		if(p[i].fi.fi.size() >= p[i - 1].fi.fi.size()){
			int f = 1;
			rep(j, p[i - 1].fi.fi.size()){
				if(p[i].fi.fi[j] != p[i - 1].fi.fi[j]){
					f = 0;
					break;
				}
			}
			ext[i] = f;
		}
	}
	int l = 1e9, r = 0;
	int hii = 0;
	rep(i, m){
		if(ext[i]){
			//we would always narrow the [l, r] range
			if(l == 1e9){
				ans[p[i].se] = 0;
				continue;
			}
			//modify the range
			repn(j, l, r + 1){
				if(s[j].size() < p[i].fi.fi.size()){
					del(j);
					l++;
					continue;
				}
				if(haS[j][(int)p[i].fi.fi.size() - 1] == haP[i][(int)p[i].fi.fi.size() - 1]) break;
				del(j);
				l++;
			}
			for(int j = r; j >= l; j--){
				if(s[j].size() < p[i].fi.fi.size()){
					del(j);
					r--;
					continue;
				}
				if(haS[j][(int)p[i].fi.fi.size() - 1] == haP[i][(int)p[i].fi.fi.size() - 1]) break;
				del(j);
				r--;
			}
			if(l > r) l = 1e9;
		}
		else{
			l = 1e9, r = 0;
			hshs.clear();
			int lo = hii, hi = n - 1;
			while(lo < hi){
				int mid = (lo + hi + 1) / 2;
				if(s[mid] < p[i].fi.fi) lo = mid;
				else hi = mid - 1;
			}
			hii = max(hii, lo);
			if(lo == 0 && s[lo] >= p[i].fi.fi) lo = -1;
			int nm = 0;
			repn(j, lo + 1, n){
				if(s[j].size() < p[i].fi.fi.size()) break;
				if(haS[j][(int)p[i].fi.fi.size() - 1] != haP[i][(int)p[i].fi.fi.size() - 1]) break;
				add(j);
				nm += s[j].size();
				l = min(l, j), r = max(r, j);
			}
		}
		ans[p[i].se] = hshs[h[i]];
	}
	rep(i, m) cout << ans[i] << '\n';
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17536 KB Output is correct
2 Correct 13 ms 17536 KB Output is correct
3 Correct 13 ms 17536 KB Output is correct
4 Correct 13 ms 17536 KB Output is correct
5 Correct 13 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 13 ms 17536 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 179496 KB Output is correct
2 Correct 476 ms 189080 KB Output is correct
3 Correct 208 ms 67704 KB Output is correct
4 Correct 210 ms 69396 KB Output is correct
5 Correct 572 ms 89296 KB Output is correct
6 Correct 592 ms 89484 KB Output is correct
7 Correct 206 ms 82104 KB Output is correct
8 Correct 234 ms 90232 KB Output is correct
9 Correct 235 ms 90488 KB Output is correct
10 Correct 255 ms 122812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 23416 KB Output is correct
2 Correct 68 ms 23160 KB Output is correct
3 Correct 80 ms 23928 KB Output is correct
4 Correct 73 ms 23032 KB Output is correct
5 Correct 75 ms 22392 KB Output is correct
6 Correct 89 ms 23500 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17536 KB Output is correct
2 Correct 13 ms 17536 KB Output is correct
3 Correct 13 ms 17536 KB Output is correct
4 Correct 13 ms 17536 KB Output is correct
5 Correct 13 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 13 ms 17536 KB Output is correct
8 Correct 460 ms 179496 KB Output is correct
9 Correct 476 ms 189080 KB Output is correct
10 Correct 208 ms 67704 KB Output is correct
11 Correct 210 ms 69396 KB Output is correct
12 Correct 572 ms 89296 KB Output is correct
13 Correct 592 ms 89484 KB Output is correct
14 Correct 206 ms 82104 KB Output is correct
15 Correct 234 ms 90232 KB Output is correct
16 Correct 235 ms 90488 KB Output is correct
17 Correct 255 ms 122812 KB Output is correct
18 Correct 94 ms 23416 KB Output is correct
19 Correct 68 ms 23160 KB Output is correct
20 Correct 80 ms 23928 KB Output is correct
21 Correct 73 ms 23032 KB Output is correct
22 Correct 75 ms 22392 KB Output is correct
23 Correct 89 ms 23500 KB Output is correct
24 Correct 459 ms 192664 KB Output is correct
25 Correct 502 ms 194428 KB Output is correct
26 Correct 447 ms 192280 KB Output is correct
27 Correct 274 ms 72692 KB Output is correct
28 Correct 507 ms 112872 KB Output is correct
29 Correct 274 ms 65144 KB Output is correct