oj.uz

Submission #468963

# Submission time Handle Problem Language Result Execution time Memory
468963 2021-08-30T09:51:39 Z sinamhdv Dabbeh (INOI20_dabbeh) C++11
0 / 100
 2000 ms 311824 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];
int pw[MAXT];
int hsh[MAXL];
vector<pii> qr[MAXL];
int seg[4 * MAXL];
vector<int> vec[MAXL];
int ssz;
int trie[MAXT][26], tn = 1;

inline void add(string &s)
{
	int v = 1;
	for (char c : s)
	{
		if (!trie[v][c - 'a']) trie[v][c - 'a'] = ++tn;
		v  = trie[v][c - 'a'];
	}
}

inline int getlcp(int i)
{
	int v = 1;
	int h = 0;
	FOR(j, i, ssz)
	{
		if (!trie[v][s[j] - 'a']) return h;
		v = trie[v][s[j] - 'a'];
		h++;
	}
	return h;
}

void setind(int i, int x)
{
	for (seg[i += MAXL] = x; i > 1; i /= 2) seg[i/2] = min(seg[i], seg[i^1]);
}

int get(int l, int r)
{
	r++;
	int res = INF;
	for (l += MAXL, r += MAXL; l < r; l /= 2, r /= 2)
	{
		if (l % 2) res = min(res, seg[l++]);
		if (r % 2) res = min(res, seg[--r]);
	}
	return res;
}

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];
		add(t[i]);
	}
	cin >> s;

	ssz = s.size();

	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 383 ms 101772 KB Output is correct
3 Correct 1004 ms 163708 KB Output is correct
4 Correct 1213 ms 195832 KB Output is correct
5 Correct 1784 ms 247420 KB Output is correct
6 Correct 1303 ms 207496 KB Output is correct
7 Execution timed out 2092 ms 311824 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 51868 KB Output is correct
2 Correct 105 ms 64372 KB Output is correct
3 Correct 87 ms 52960 KB Output is correct
4 Correct 76 ms 40104 KB Output is correct
5 Correct 82 ms 38688 KB Output is correct
6 Correct 73 ms 59840 KB Output is correct
7 Correct 85 ms 64928 KB Output is correct
8 Correct 78 ms 56672 KB Output is correct
9 Correct 84 ms 61196 KB Output is correct
10 Correct 96 ms 68376 KB Output is correct
11 Correct 117 ms 55328 KB Output is correct
12 Correct 100 ms 51684 KB Output is correct
13 Correct 103 ms 77120 KB Output is correct
14 Correct 99 ms 70268 KB Output is correct
15 Correct 75 ms 34156 KB Output is correct
16 Execution timed out 2057 ms 59884 KB Time limit exceeded
17 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 383 ms 101772 KB Output is correct
3 Correct 1004 ms 163708 KB Output is correct
4 Correct 1213 ms 195832 KB Output is correct
5 Correct 1784 ms 247420 KB Output is correct
6 Correct 1303 ms 207496 KB Output is correct
7 Execution timed out 2092 ms 311824 KB Time limit exceeded
8 Halted 0 ms 0 KB -