#include <bits/stdc++.h>
#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)
#define WTF cout << "WTF" << endl
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int N = 1e6 + 7;
const int LOG = 22;
const char C = ' ';
//#define endl '\n'
#define lc now << 1
#define rc now << 1 | 1
int q, m, n, pw, len;
int tmp[N], mid[N];
int rnk[LOG][N];
PII p[N];
string ts[N], s, ns;
struct IntMaxSeg {
int tree[N << 2];
int build(int now = 1, int ls = 0, int rs = n) {
if (ls == rs) return tree[now] = tmp[ls];
int mid = (ls + rs) >> 1;
return tree[now] = max(build(lc, ls, mid), build(rc, mid + 1, rs));
}
int get(int lq, int rq, int now = 1, int ls = 0, int rs = n) {
if (rq < lq || rq < ls || rs < lq) return 0;
if (lq <= ls && rs <= rq) return tree[now];
int mid = (ls + rs) >> 1;
return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
}
} dp[LOG];
void init() {
cin >> q >> m;
F0R(i, q) {
cin >> ts[i];
ns += C + ts[i];
}
cin >> s;
n = s.length();
ns += C + s;
len = ns.length();
}
inline bool cmp(const PII &a, const PII &b) {
//cout << "rnk[0][24] rnk[0][25] " << rnk[0][24] << ' ' << rnk[0][25] << endl;
//cout << "for " << a.F << ' ' << b.F << " rnks are " << rnk[pw - 1][a.F] << ", " << rnk[pw - 1][b.F] << endl;
//cout << "and pw = " << pw << endl;
if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return (rnk[pw - 1][a.F] < rnk[pw - 1][b.F]);
if (max(a.F, b.F) + (1 << (pw - 1)) >= len) return (a.F > b.F);
return (rnk[pw - 1][a.F + (1 << (pw - 1))] < rnk[pw - 1][b.F + (1 << (pw - 1))]);
}
void buildSA() {
int c = -1;
F0R(i, len) {
rnk[0][i] = ns[i];
p[i].F = i;
if (i && ns[i - 1] == C) p[i].S = c--;
}
/*cout << ns << endl;
cout <<len << endl;
cout << "rnk[0] ";
//F0R(i, len) cout << rnk[0][i] << ' '; cout << endl;
cout << rnk[0][24] << ' ' << rnk[0][25] << endl;*/
c = n;
R0F(i, len) {
if (ns[i] == C) break;
p[i].S = c--;
}
//cout << rnk[0][24] << ' ' << rnk[0][25] << endl;
for(pw = 1; pw < LOG; pw++) {
sort(p, p + len, cmp);
//cout << rnk[0][24] << ' ' << rnk[0][25] << endl;
//cout << "after sort ";
//F0R(i, n) cout << p[i].F << ' '; cout << endl;
//cout <<"pw = " << pw << endl;
rnk[pw][ p[0].F ] = 0;
FOR(i, 1, len) {
rnk[pw][ p[i].F ] = rnk[pw][ p[i - 1].F ] + cmp(p[i - 1], p[i]);
//cout << "cmp(" << p[i - 1].F << ", " << p[i].F << ") = " << cmp(p[i - 1], p[i]) << endl;
}
//cout << "rnk ";
//F0R(i, len) cout << rnk[pw][i] << ' '; cout << endl;
}
return;
}
inline int lcp(int a, int b) {
int ret = 0;
R0F(i, LOG) {
if (max(a, b) + (1 << i) > len) continue;
if (rnk[i][a] != rnk[i][b]) continue;
ret |= (1 << i);
a += (1 << i);
b += (1 << i);
}
return ret;
}
void dpBase() {
int lst = -1;
F0R(i, len) {
if (p[i].S < 0)
lst = p[i].F;
if (p[i].S > 0 && lst != -1)
tmp[ p[i].S - 1 ] = lcp(lst, p[i].F);
}
lst = -1;
R0F(i, len) {
if (p[i].S < 0)
lst = p[i].F;
if (p[i].S > 0 && lst != -1)
tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1], lcp(lst, p[i].F));
}
/*F0R(i, len) if (p[i].S > 0) F0R(j, len) if (p[j].S < 0) {
tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1 ], lcp(p[i].F, p[j].F));
}*/
F0R(i, n + 1) tmp[i] += i;
dp[0].build();
//F0R(i, n + 1) cout << dp[0].get(i, i) << ' '; cout << endl;
return;
}
void calcLayer(int id) {
F0R(i, n + 1) {
int x = dp[id - 1].get(i, i);
tmp[i] = dp[id - 1].get(i, x);
}
dp[id].build();
//F0R(i, n + 1) cout << dp[id].get(i, i) << ' '; cout << endl;
}
void handleQuery() {
int l, r;
cin >> l >> r;
r--;
int now = l, sum = 0;
if (dp[LOG - 1].get(l, l) <= r) {
cout << -1 << endl;
return;
}
R0F(i, LOG) {
int x = dp[i].get(l, now);
if (x <= r) {
sum += (1 << i);
now = x;
}
}
cout << sum + 1 << endl;
}
int main() {
IOS;
init();
buildSA();
dpBase();
FOR(i, 1, LOG) calcLayer(i);
while(m--) handleQuery();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
32084 KB |
Output is correct |
| 2 |
Correct |
1347 ms |
70092 KB |
Output is correct |
| 3 |
Correct |
1216 ms |
59716 KB |
Output is correct |
| 4 |
Correct |
1610 ms |
71012 KB |
Output is correct |
| 5 |
Correct |
1491 ms |
67860 KB |
Output is correct |
| 6 |
Correct |
1815 ms |
79536 KB |
Output is correct |
| 7 |
Correct |
1728 ms |
81392 KB |
Output is correct |
| 8 |
Correct |
1710 ms |
82864 KB |
Output is correct |
| 9 |
Correct |
1563 ms |
76152 KB |
Output is correct |
| 10 |
Correct |
943 ms |
45788 KB |
Output is correct |
| 11 |
Correct |
1364 ms |
77252 KB |
Output is correct |
| 12 |
Correct |
962 ms |
54780 KB |
Output is correct |
| 13 |
Correct |
1211 ms |
67148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2075 ms |
136700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
32084 KB |
Output is correct |
| 2 |
Correct |
1347 ms |
70092 KB |
Output is correct |
| 3 |
Correct |
1216 ms |
59716 KB |
Output is correct |
| 4 |
Correct |
1610 ms |
71012 KB |
Output is correct |
| 5 |
Correct |
1491 ms |
67860 KB |
Output is correct |
| 6 |
Correct |
1815 ms |
79536 KB |
Output is correct |
| 7 |
Correct |
1728 ms |
81392 KB |
Output is correct |
| 8 |
Correct |
1710 ms |
82864 KB |
Output is correct |
| 9 |
Correct |
1563 ms |
76152 KB |
Output is correct |
| 10 |
Correct |
943 ms |
45788 KB |
Output is correct |
| 11 |
Correct |
1364 ms |
77252 KB |
Output is correct |
| 12 |
Correct |
962 ms |
54780 KB |
Output is correct |
| 13 |
Correct |
1211 ms |
67148 KB |
Output is correct |
| 14 |
Execution timed out |
2075 ms |
136700 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
