oj.uz

답안 #468960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468960 2021-08-30T09:49:25 Z sinamhdv Dabbeh (INOI20_dabbeh) C++11
0 / 100
 2000 ms 186952 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, 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];
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21324 KB Output is correct
2 Correct 525 ms 101900 KB Output is correct
3 Correct 1719 ms 163756 KB Output is correct
4 Execution timed out 2082 ms 186952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 51864 KB Output is correct
2 Correct 205 ms 64588 KB Output is correct
3 Correct 178 ms 53164 KB Output is correct
4 Correct 144 ms 40204 KB Output is correct
5 Correct 147 ms 38756 KB Output is correct
6 Correct 118 ms 60120 KB Output is correct
7 Correct 131 ms 65308 KB Output is correct
8 Correct 128 ms 56816 KB Output is correct
9 Correct 130 ms 61464 KB Output is correct
10 Correct 143 ms 68748 KB Output is correct
11 Correct 189 ms 55512 KB Output is correct
12 Correct 204 ms 51808 KB Output is correct
13 Correct 207 ms 77116 KB Output is correct
14 Correct 195 ms 70256 KB Output is correct
15 Correct 134 ms 34148 KB Output is correct
16 Execution timed out 2081 ms 59888 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21324 KB Output is correct
2 Correct 525 ms 101900 KB Output is correct
3 Correct 1719 ms 163756 KB Output is correct
4 Execution timed out 2082 ms 186952 KB Time limit exceeded
5 Halted 0 ms 0 KB -