oj.uz

Submission #468959

# Submission time Handle Problem Language Result Execution time Memory
468959 2021-08-30T09:44:43 Z sinamhdv Dabbeh (INOI20_dabbeh) C++11
0 / 100
 2000 ms 161908 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000000363;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm = 727;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 10100;
const int MAXL = 300100;
const int MAXT = 500100;

int n, q;
string t[MAXN];
string s;
int lcp[MAXL];
int qans[MAXL];
set<int> hst;
int pw[MAXT];
int hsh[MAXL];
vector<pii> qr[MAXL];
int seg[4 * MAXL];
vector<int> vec[MAXL];
int ssz;

inline int gethash(int l, int r)
{
	return (mod + (hsh[r + 1] - hsh[l] * (ll)pw[r - l + 1]) % mod) % mod;
}

inline int getlcp(int i)
{
	int l = 0, r = (int)s.size() - i + 1;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (hst.count(gethash(i, i + mid - 1))) l = mid;
		else r = mid;
	}
	return l;
}

void setind(int i, int x, int v = 1, int l = 0, int r = ssz - 1)
{
	if (l == r)
	{
		seg[v] = x;
		return;
	}
	int mid = (r + l) / 2;
	if (i <= mid) setind(i, x, 2*  v, l, mid );
	else setind(i, x, 2 *v + 1, mid + 1, r);
	seg[v] = min(seg[2 *  v], seg[2 * v + 1]);
}

int get(int L, int R, int v = 1, int l = 0, int r = ssz -1)
{
	if (l > R || r < L) return INF;
	if (l >= L && r <= R) return seg[v];
	int mid = (r + l) / 2;
	return min(get(L, R, 2 * v , l, mid), get(L, R, 2 * v + 1, mid + 1, r));
}

int32_t main(void)
{
	fast_io;
	
	pw[0] = 1;
	FOR(i, 1, MAXT) pw[i] = (ll)pw[i - 1] * prm % mod;

	cin >> n >> q;
	FOR(i, 0, n)
	{
		cin >> t[i];
		// prehash
		ll h = 0;
		for (char c : t[i])
		{
			h = (prm * h + c) % mod;
			hst.insert(h);
		}
	}
	cin >> s;

	ssz = s.size();

	// prehash
	FOR(i, 1, (int)s.size() + 1) hsh[i] = (hsh[i - 1] * (ll)prm + s[i - 1]) % mod;

	FOR(i, 0, (int)s.size()) lcp[i] = getlcp(i);

	dbgr(lcp, lcp + (int)s.size());

	FOR(i, 0, (int)s.size()) if (lcp[i])
	{
		vec[i + lcp[i] - 1].pb(i);
	}

	FOR(i, 0, q)
	{
		int l, r;
		cin >> l >> r;
		r--;
		qr[r].pb({l, i});
	}

	fill(seg, seg + 4 * MAXL, INF);

	for (int r = (int)s.size() - 1; r >= 0; r--)
	{
		dbg(r);
		for (int u : vec[r])
		{
			dbg(u);
			dbg(seg[1]);
			setind(u, u);
		}
		for (pii p : qr[r])
		{
			dbg(p.fr);
			int nxt = get(p.fr, ssz - 1);
			dbg(p.sc);
			dbg(nxt);
			if (nxt > r)
			{
				qans[p.sc] = -1;
				continue;
			}
			qans[p.sc]++;
			if (nxt > p.fr) qr[nxt - 1].pb(p);
		}

		dbg("=================\n");
	}

	FOR(i, 0, q) cout << qans[i] << endl;

	return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21324 KB Output is correct
2 Correct 774 ms 82540 KB Output is correct
3 Correct 1768 ms 150292 KB Output is correct
4 Execution timed out 2086 ms 161908 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 39860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21324 KB Output is correct
2 Correct 774 ms 82540 KB Output is correct
3 Correct 1768 ms 150292 KB Output is correct
4 Execution timed out 2086 ms 161908 KB Time limit exceeded
5 Halted 0 ms 0 KB -