QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #132282 | #4255. Sone2 | NOI_AK_ME | 100 ✓ | 152ms | 58764kb | C++11 | 27.5kb | 2023-07-29 12:48:53 | 2023-07-29 12:48:55 |
Judging History
answer
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int sa[N], X[N], Y[N], a[N], b[N], h[N], r[N], rnk[N], fk[20][N], iden[20][N], lg[N], lcp[N], n, m;
struct segment_tree
{
int l, r, T, x, lazy_lcp, lazy_pos;
int hash_value, max_pos, max_lcp, cnt;
};
segment_tree tree[1 << 18], now, nw, bw;
const int mod = 1000 * 1000 * 1000 + 9;
const int base = 107;
int mei_you_yi_yi_de_shu_ju;
int aaa[110000], str[110000], ex[2 * N], hs[2][101000], lc[101000], num_q, dist[2 * N], to[2 * N], list[2 * N],
cnt_list, pos[2 * N], sz[2 * N];
int ha[2 * N], stk[2 * N], idx[2 * N], pa[2 * N];
int query(int ip1, int left, int right)
{
int ret;
ret = hs[ip1][right + 1] - (int)((long long)hs[ip1][left] * (long long)ex[right - left + 1] % mod);
ret = (ret % mod + mod) % mod;
return ret;
}
struct pp
{
int id, x;
bool operator<(const pp &temp) const
{
return x < temp.x;
}
};
vector<pp> adj[2 * N], tadj[2 * N];
struct segment
{
int l, r, hash_value;
};
segment sg[2 * N];
int cnt_sg;
bool cmp(int id1, int id2)
{
return rnk[id1] < rnk[id2];
}
bool comp(int *r, int a, int b, int le)
{
return r[a] == r[b] && r[a + le] == r[b + le];
}
void sort(int *Rank, int *Id, int n, int m)
{
std::fill(b, b + m, 0);
for (int i = n - 1; i >= 0; i--)
b[Rank[i]]++;
for (int i = 1; i < m; i++)
b[i] += b[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--b[Rank[Id[i]]]] = Id[i];
}
void suffix(int n, int m = 100001)
{
int *Rank = X, *Id = Y, p = 1;
for (int i = 0; i < n; i++)
Rank[i] = a[i], Id[i] = i;
sort(Rank, Id, n, m);
for (int j = 1; p < n; j <<= 1)
{
p = 0;
for (int i = n - j; i < n; i++)
Id[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= j)
Id[p++] = sa[i] - j;
sort(Rank, Id, n, p);
std::swap(Rank, Id);
Rank[sa[0]] = 0, p = 1;
for (int i = 1; i < n; i++)
Rank[sa[i]] = comp(Id, sa[i - 1], sa[i], j) ? p - 1 : p++;
m = p;
}
}
void LCP(int *str, int left, int right)
{
int i, j, k, len;
len = right - left + 1;
k = 0;
for (i = left; i <= right; i++)
{
if (rnk[i] == len - 1)
lcp[rnk[i]] = k = 0;
else
{
if (k > 0)
k--;
j = sa[rnk[i] + 1];
for (; str[i + k] == str[j + k]; k++)
;
lcp[rnk[i]] = k;
}
}
}
int rmq(int id1, int id2, int &ix)
{
int ip1, ip2, le, ri, id;
if (id1 == id2)
return m - id1;
ip1 = rnk[id1];
ip2 = rnk[id2];
if (ip1 < ip2)
{
le = ip1;
ri = ip2 - 1;
}
else
{
le = ip2;
ri = ip1 - 1;
}
id = lg[ri - le + 1];
int ret;
if (fk[id][le] <= fk[id][ri + 1 - (1 << id)])
{
ret = fk[id][le];
ix = iden[id][le];
}
else
{
ret = fk[id][ri + 1 - (1 << id)];
ix = iden[id][ri + 1 - (1 << id)];
}
return ret;
}
void got(int left, int right, int dx, int il)
{
int i, j, s, p, q, vs, id, ip;
vs = rmq(sa[left], sa[right], id);
if (vs == n - sa[left] && left != right)
{
got(left + 1, right, dx, il);
return;
}
if (vs > dx)
{
sg[cnt_sg].l = sa[left] + dx;
sg[cnt_sg++].r = sa[left] + vs - 1;
sg[cnt_sg - 1].hash_value = query(1, sa[left] + dx, sa[left] + vs - 1);
pp now;
now.id = cnt_sg - 1;
now.x = str[sa[left] + dx];
adj[il].push_back(now);
tadj[il].push_back(now);
il = cnt_sg - 1;
}
ip = left;
if (left != right)
{
got(left, id, vs, il);
got(id + 1, right, vs, il);
}
}
void get_dist(int id)
{
int top = 0, i, j, s, p, q, ch = -1, ip;
dist[id] = 0;
to[id] = id;
stk[top++] = id;
idx[id] = 0;
while (top)
{
id = stk[top - 1];
if (idx[id] == adj[id].size())
{
top--;
if (id != 0 && dist[pa[id]] < dist[id] + 1)
{
to[pa[id]] = to[id];
dist[pa[id]] = dist[id] + 1;
}
}
else
{
ip = adj[id][idx[id]].id;
idx[id]++;
stk[top++] = ip;
idx[ip] = 0;
dist[ip] = 0;
pa[ip] = id;
to[ip] = ip;
}
}
}
void dfs(int id)
{
int i, j, s, p, q, ip, top = 0;
list[cnt_list++] = id;
pos[id] = cnt_list - 1;
stk[top++] = id;
idx[id] = 0;
while (top)
{
id = stk[top - 1];
if (idx[id] == adj[id].size())
top--;
else
{
ip = adj[id][idx[id]].id;
idx[id]++;
stk[top++] = ip;
idx[ip] = 0;
list[cnt_list++] = ip;
pos[ip] = cnt_list - 1;
}
}
}
int power(int a, long long n, int mod)
{
int ret;
if (n == 0)
return 1;
ret = power(a, n / 2, mod);
ret = (int)((long long)ret * (long long)ret % mod);
if (n % 2)
ret = (int)((long long)ret * (long long)a % mod);
return ret;
}
int fangwen(int left, int right, int l1, int len1, int l2, int len2, int &len, int &vl)
{
int i, mid, nvl, vs, tr;
tr = vl;
int lf = left;
while (left <= right)
{
mid = (left + right) >> 1;
bool ok = true;
if (len + sz[mid + 1] - sz[lf] > len1 + len2)
ok = false;
else
{
nvl = (int)((long long)vl * (long long)ex[sz[mid + 1] - sz[lf]] % mod);
int vm = ha[mid + 1] - (int)((long long)ha[lf] * (long long)ex[sz[mid + 1] - sz[lf]] % mod);
vm = (vm % mod + mod) % mod;
nvl = (nvl + vm) % mod;
vs = query(1, l1, l1 + min(len1, len + sz[mid + 1] - sz[lf]) - 1);
if (len + sz[mid + 1] - sz[lf] > len1)
{
vs = (int)((long long)vs * (long long)ex[len + sz[mid + 1] - sz[lf] - len1] % mod);
vs = (vs + query(1, l2, l2 + len + sz[mid + 1] - sz[lf] - len1 - 1)) % mod;
}
if (nvl != vs)
ok = false;
}
if (ok)
{
tr = nvl;
left = mid + 1;
}
else
right = mid - 1;
}
vl = tr;
len += sz[right + 1] - sz[lf];
return right;
}
int binary(int left, int right, vector<pp> &adj, int x)
{
int mid;
while (left <= right)
{
mid = (left + right) >> 1;
if (adj[mid].x < x)
left = mid + 1;
else if (adj[mid].x > x)
right = mid - 1;
else
return mid;
}
return -1;
}
void merge(segment_tree ll, segment_tree rr, segment_tree &ret)
{
ret.max_pos = max(ll.max_pos, rr.max_pos);
ret.max_lcp = max(ll.max_lcp, rr.max_lcp);
ret.cnt = 0;
if (ret.max_lcp == ll.max_lcp)
ret.cnt = ll.cnt;
if (ret.max_lcp == rr.max_lcp)
ret.cnt += rr.cnt;
int vm = (int)((long long)ll.hash_value * (long long)ex[rr.r - rr.l + 1] % mod);
ret.hash_value = (vm + rr.hash_value) % mod;
}
void build(int left, int right, int id)
{
int l = 2 * id + 1, r = 2 * id + 2, mid = (left + right) >> 1;
tree[id].l = left;
tree[id].r = right;
tree[id].hash_value = query(0, left, right);
tree[id].T = 0;
tree[id].lazy_lcp = tree[id].lazy_pos = -1;
if (left == right)
{
tree[id].max_lcp = lc[left];
tree[id].max_pos = left + lc[left];
tree[id].cnt = 1;
return;
}
build(left, mid, l);
build(mid + 1, right, r);
merge(tree[l], tree[r], tree[id]);
}
void update_lcp(int pos, int max_lcp, int max_pos, int id);
void zz(int id);
void update_hash(int pos, int vl, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].l == tree[id].r)
{
tree[id].hash_value = vl;
return;
}
if (tree[l].r < pos)
{
update_hash(pos, vl, r);
zz(l);
}
else
{
update_hash(pos, vl, l);
zz(r);
}
merge(tree[l], tree[r], tree[id]);
}
segment_tree find(int left, int right, int pos, bool flag, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
segment_tree ret;
zz(id);
if (tree[id].max_pos < pos || tree[id].r < left || tree[id].l > right)
{
ret.max_pos = -1;
return ret;
}
if (tree[id].l == tree[id].r)
return tree[id];
if (flag == 0)
{
ret = find(left, right, pos, flag, r);
if (ret.max_pos < pos)
ret = find(left, right, pos, flag, l);
else
zz(l);
}
else
{
ret = find(left, right, pos, flag, l);
if (ret.max_pos < pos)
ret = find(left, right, pos, flag, r);
else
zz(r);
}
merge(tree[l], tree[r], tree[id]);
return ret;
}
int find(int pos, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].l == tree[id].r)
return tree[id].max_pos;
int ret;
if (tree[l].r < pos)
{
ret = find(pos, r);
zz(l);
}
else
{
ret = find(pos, l);
zz(r);
}
merge(tree[l], tree[r], tree[id]);
return ret;
}
int find(int left, int right, int lp, int rp, int &vl, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].r < left || tree[id].l > right)
{
if (tree[id].r < left)
return tree[id].r;
return tree[id].l - 1;
}
if (tree[id].l >= left && tree[id].r <= right)
{
int nvl;
nvl = (int)((long long)vl * (long long)ex[tree[id].r - tree[id].l + 1] % mod);
nvl = (nvl + tree[id].hash_value) % mod;
if (nvl == hs[1][rp + tree[id].r - right +
1]) // if(nvl[0]==hs[1][0][rp+tree[id].r-right+1]&&nvl[1]==hs[1][1][rp+tree[id].r-right+1])
{
// for(int i=0;i<2;i++)
// vl[i]=nvl[i];
vl = nvl;
return tree[id].r;
}
}
if (tree[id].l == tree[id].r)
return tree[id].l - 1;
int ret = find(left, right, lp, rp, vl, l);
if (ret == tree[l].r)
ret = find(left, right, lp, rp, vl, r);
else
zz(r);
merge(tree[l], tree[r], tree[id]);
return ret;
}
void update(int left, int right, int T, int x, int max_lcp, int max_pos, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].r < left || tree[id].l > right)
return;
if (tree[id].l >= left && tree[id].r <= right)
{
tree[id].T = T;
tree[id].x = x;
if (max_lcp >= 0)
tree[id].lazy_lcp = max_lcp;
if (max_pos >= 0)
tree[id].lazy_pos = max_pos;
zz(id);
return;
}
update(left, right, T, x, max_lcp, max_pos, l);
update(left, right, T, x, max_lcp, max_pos, r);
merge(tree[l], tree[r], tree[id]);
}
void update(int pos, int max_lcp, int max_pos, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].l == tree[id].r)
{
tree[id].max_lcp = max_lcp;
tree[id].max_pos = max_pos;
tree[id].cnt = 1;
return;
}
if (tree[l].r < pos)
{
update(pos, max_lcp, max_pos, r);
zz(l);
}
else
{
update(pos, max_lcp, max_pos, l);
zz(r);
}
merge(tree[l], tree[r], tree[id]);
}
segment_tree find(int left, int right, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
segment_tree ret, ll, rr;
zz(id);
if (tree[id].r < left || tree[id].l > right)
{
ret.max_lcp = -1;
return ret;
}
if (tree[id].l >= left && tree[id].r <= right)
return tree[id];
ll = find(left, right, l);
rr = find(left, right, r);
ret = ll;
if (ret.max_lcp < rr.max_lcp)
ret = rr;
else if (ret.max_lcp == rr.max_lcp)
ret.cnt += rr.cnt;
merge(tree[l], tree[r], tree[id]);
return ret;
}
void get_hash(int left, int right, int &vs, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
if (tree[id].l == left && tree[id].r == right)
{
vs = (int)((long long)vs * (long long)ex[tree[id].r - tree[id].l + 1] % mod);
vs = (vs + tree[id].hash_value) % mod;
return;
}
if (tree[l].r < left)
get_hash(left, right, vs, r);
else if (tree[r].l > right)
get_hash(left, right, vs, l);
else
{
get_hash(left, tree[l].r, vs, l);
get_hash(tree[r].l, right, vs, r);
}
}
int main()
{
int i, j, s, p, q, low, high, mid, id, vl, pm, k, ip;
for (i = 2; i <= 100000; i++)
lg[i] = lg[i / 2] + 1;
scanf("%d", &mei_you_yi_yi_de_shu_ju);
for (i = 0; i <= 200000; i++)
{
if (i == 0)
ex[i] = 1;
else
ex[i] = (int)((long long)ex[i - 1] * (long long)base % mod);
}
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &aaa[i]);
scanf("%d", &m);
for (i = 0; i < m; i++)
scanf("%d", &str[i]);
memset(hs, 0, sizeof(hs));
for (i = 1; i <= n; i++)
{
hs[0][i] = (int)((long long)hs[0][i - 1] * (long long)base % mod);
hs[0][i] = (hs[0][i] + aaa[i - 1]) % mod;
}
for (i = 1; i <= m; i++)
{
hs[1][i] = (int)((long long)hs[1][i - 1] * (long long)base % mod);
hs[1][i] = (hs[1][i] + str[i - 1]) % mod;
}
for (i = 0; i < n; i++)
{
low = 0;
high = min(n - i + 1, m);
while (low <= high)
{
mid = (low + high) >> 1;
if (query(0, i, i + mid - 1) == query(1, 0, mid - 1))
low = mid + 1;
else
high = mid - 1;
}
lc[i] = high;
}
for (i = 0; i < m; i++)
a[i] = str[i];
a[n] = 0;
suffix(m + 1);
for (i = 1; i <= m; i++)
sa[i - 1] = sa[i];
for (i = 0; i < m; i++)
rnk[sa[i]] = i;
LCP(str, 0, m - 1);
for (i = 0; i < m; i++)
{
fk[0][i] = lcp[i];
iden[0][i] = i;
}
for (k = 1; (1 << k) <= m; k++)
for (i = 0; i + (1 << k) <= m; i++)
{
if (fk[k - 1][i] <= fk[k - 1][i + (1 << (k - 1))])
{
fk[k][i] = fk[k - 1][i];
iden[k][i] = iden[k - 1][i];
}
else
{
fk[k][i] = fk[k - 1][i + (1 << (k - 1))];
iden[k][i] = iden[k - 1][i + (1 << (k - 1))];
}
}
sg[0].hash_value = 0;
sg[0].l = 0;
sg[0].r = -1;
cnt_sg = 1;
got(0, m - 1, 0, 0);
for (i = 0; i < cnt_sg; i++)
sort(tadj[i].begin(), tadj[i].end());
get_dist(0);
for (i = 0; i < cnt_sg; i++)
{
for (j = 0; j < adj[i].size(); j++)
{
id = adj[i][j].id;
if (to[i] == to[id])
break;
}
if (j < adj[i].size())
swap(adj[i][0], adj[i][j]);
}
cnt_list = 0;
dfs(0);
build(0, n - 1, 0);
ha[0] = 0;
sz[0] = 0;
for (i = 1; i <= cnt_sg; i++)
{
sz[i] = sz[i - 1] + sg[list[i - 1]].r - sg[list[i - 1]].l + 1;
ha[i] = (int)((long long)ha[i - 1] * (long long)ex[sg[list[i - 1]].r - sg[list[i - 1]].l + 1] % mod);
ha[i] = (ha[i] + sg[list[i - 1]].hash_value);
}
scanf("%d", &num_q);
int flag, aa, bb, cc, dd;
while (num_q--)
{
scanf("%d%d%d", &flag, &aa, &bb);
if (flag == 4)
scanf("%d%d", &cc, &dd);
aa--;
if (flag >= 2)
bb--;
if (flag == 4)
{
cc--;
dd--;
}
if (flag == 1)
{
if (aaa[aa] != bb)
{
aaa[aa] = bb;
update_hash(aa, bb, 0);
now = find(0, aa, aa, 0, 0);
while (true)
{
if (now.max_pos >= aa)
{
nw = find(0, now.l - 1, aa, 0, 0);
if (nw.max_pos >= aa)
{
low = 0;
high = min(m, nw.l / (now.l - nw.l));
int vs, vm;
vs = vm = 0;
if (nw.l <= now.l - 1)
get_hash(nw.l, now.l - 1, vs, 0);
if (now.l <= aa - 1)
get_hash(now.l, aa - 1, vm, 0);
while (low <= high)
{
mid = (low + high) >> 1;
bool ok = true;
int give;
give = power(base, mid * (now.l - nw.l), mod) - 1;
if (give < 0)
give += mod;
int vp = power(base, now.l - nw.l, mod) - 1;
if (vp < 0)
vp += mod;
give = (int)((long long)give * (long long)power(vp, mod - 2, mod) % mod);
give = (int)((long long)give * (long long)vs % mod);
if (give != hs[1][mid * (now.l - nw.l)])
{
ok = false;
// break;
}
if (ok)
{
if (find(nw.l - mid * (now.l - nw.l), 0) < aa)
ok = false;
}
if (ok)
low = mid + 1;
else
high = mid - 1;
}
bw = find(nw.l - high * (now.l - nw.l), nw.l - high * (now.l - nw.l), aa, 0, 0);
int ll, rr;
if (now.max_pos > aa)
{
ll = nw.l - high * (now.l - nw.l);
if (bw.max_pos == aa)
ll += now.l - nw.l;
rr = now.l;
if (now.l != aa)
rr = nw.l;
if (ll <= rr)
update(ll, rr, now.l - nw.l, now.l % (now.l - nw.l), -1, aa, 0);
if (bw.max_pos == aa)
{
vl = 0;
pm = find(bw.l, bw.l + min(n - bw.l, m) - 1, 0, min(n - bw.l, m) - 1, vl, 0);
update(bw.l, pm - bw.l + 1, pm + 1, 0);
}
}
else
{
low = 0;
high = (now.l - bw.l) / (now.l - nw.l);
vl = 0;
pm = find(now.l, now.l + min(n - now.l, m) - 1, 0, min(n - now.l, m) - 1, vl, 0);
while (low <= high)
{
mid = (low + high) >> 1;
int x = now.l - mid * (now.l - nw.l);
vl = 0;
if (find(x, x + min(n - x, m) - 1, 0, min(n - x, m) - 1, vl, 0) == pm)
low = mid + 1;
else
high = mid - 1;
}
ll = now.l - high * (now.l - nw.l);
rr = now.l;
if (now.l != aa)
rr -= now.l - nw.l;
if (ll <= rr)
{
vl = 0;
update(ll, rr, now.l - nw.l, now.l % (now.l - nw.l), -1, pm + 1, 0);
}
ll = bw.l;
rr = now.l - (low + 1) * (now.l - nw.l);
if (ll <= rr)
{
vl = 0;
update(ll, rr, now.l - nw.l, now.l % (now.l - nw.l),
find(bw.l, bw.l + min(n - bw.l, m) - 1, 0, min(n - bw.l, m) - 1, vl, 0) -
bw.l + 1,
-1, 0);
}
int x = now.l - low * (now.l - nw.l);
if ((x != now.l || now.l != aa) && x >= bw.l && x <= now.l)
{
vl = 0;
pm = find(x, x + min(n - x, m) - 1, 0, min(n - x, m) - 1, vl, 0);
update_lcp(x, pm + 1 - x, pm + 1, 0);
}
}
now = bw;
if (now.l == 0)
break;
}
else
{
if (now.l == aa)
{
if (now.max_pos > aa)
now.max_pos = aa;
else
{
vl = 0;
now.max_pos =
find(now.l, now.l + min(n - now.l, m) - 1, 0, min(n - now.l, m) - 1, vl, 0) + 1;
}
now.max_lcp = now.max_pos - now.l;
update(now.l, now.max_lcp, now.max_pos, 0);
}
break;
}
}
else
break;
}
}
now = find(1, 1, 1, 0, 0);
flag = 2;
aa = 0;
bb = n - 1;
}
if (flag == 2)
{
now = find(aa, bb, bb + 1, 1, 0);
if (now.max_pos < 0)
{
now.max_lcp = -1;
now.l = bb + 1;
}
else
now.max_lcp = bb + 1 - now.l;
if (now.l > aa)
bw = find(aa, now.l - 1, 0);
else
bw.max_lcp = -1;
if (now.max_lcp < bw.max_lcp)
now = bw;
else if (now.max_lcp == bw.max_lcp)
now.cnt += bw.cnt;
printf("%d %d\n", now.max_lcp, now.cnt);
}
if (flag == 3)
{
low = 0;
high = min(m - aa, m - bb);
while (low <= high)
{
mid = (low + high) >> 1;
if (query(1, aa, aa + mid - 1) == query(1, bb, bb + mid - 1))
low = mid + 1;
else
high = mid - 1;
}
printf("%d\n", high);
}
if (flag == 4)
{
id = 0;
vl = 0;
int len = 0;
while (true)
{
ip = fangwen(pos[id], pos[to[id]], aa, bb - aa + 1, cc, dd - cc + 1, len, vl);
if (len >= bb - aa + 1 + dd - cc + 1)
break;
if (ip == pos[id] - 1)
{
if (len + sg[id].r - sg[id].l + 1 >= bb - aa + 1 + dd - cc + 1)
{
int vs, nvl;
nvl = (int)((long long)vl * (long long)ex[bb - aa + 1 + dd - cc + 1 - len] % mod);
nvl = (nvl + query(1, sg[id].l, sg[id].l + bb - aa + 1 + dd - cc + 1 - len - 1)) % mod;
vs = (int)((long long)query(1, aa, bb) * (long long)ex[dd - cc + 1] % mod);
vs = (vs + query(1, cc, dd)) % mod;
if (nvl == vs)
len = bb - aa + 1 + dd - cc + 1;
}
break;
}
id = list[ip];
int ch;
if (len >= bb - aa + 1)
ch = str[cc + len - (bb - aa + 1)];
else
ch = str[aa + len];
ip = binary(0, (int)(tadj[id].size()) - 1, tadj[id], ch);
if (ip < 0)
break;
id = tadj[id][ip].id;
}
if (len == bb - aa + 1 + dd - cc + 1)
puts("yes");
else
puts("no");
}
}
return 0;
}
void zz(int id)
{
if (tree[id].T == 0)
return;
int pos = tree[id].l + ((tree[id].x - tree[id].l) % tree[id].T + tree[id].T) % tree[id].T;
if (pos > tree[id].r)
return;
tree[id].max_lcp = tree[id].max_pos = -1;
if (tree[id].lazy_lcp >= 0)
{
tree[id].max_lcp = tree[id].lazy_lcp;
tree[id].max_pos = pos + tree[id].lazy_lcp;
tree[id].cnt = (tree[id].r - pos) / tree[id].T + 1;
}
if (tree[id].lazy_pos >= 0)
{
tree[id].max_pos = tree[id].lazy_pos;
tree[id].max_lcp = tree[id].lazy_pos - pos;
tree[id].cnt = 1;
}
int l = 2 * id + 1, r = 2 * id + 2;
if (pos <= tree[l].r)
{
tree[l].T = tree[id].T;
tree[l].x = tree[id].x;
if (tree[id].lazy_pos >= 0)
tree[l].lazy_pos = tree[id].lazy_pos;
if (tree[id].lazy_lcp >= 0)
tree[l].lazy_lcp = tree[id].lazy_lcp;
}
pos = tree[r].l + ((tree[id].x - tree[r].l) % tree[id].T + tree[id].T) % tree[id].T;
if (pos <= tree[r].r)
{
tree[r].T = tree[id].T;
tree[r].x = tree[id].x;
if (tree[id].lazy_pos >= 0)
tree[r].lazy_pos = tree[id].lazy_pos;
if (tree[id].lazy_lcp >= 0)
tree[r].lazy_lcp = tree[id].lazy_lcp;
}
tree[id].T = 0;
tree[id].lazy_pos = tree[id].lazy_lcp = -1;
}
void update_lcp(int pos, int max_lcp, int max_pos, int id)
{
int l = 2 * id + 1, r = 2 * id + 2;
zz(id);
if (tree[id].l == tree[id].r)
{
tree[id].max_lcp = max_lcp;
tree[id].max_pos = max_pos;
return;
}
if (tree[l].r < pos)
{
update_lcp(pos, max_lcp, max_pos, r);
zz(l);
}
else
{
update_lcp(pos, max_lcp, max_pos, l);
zz(r);
}
merge(tree[l], tree[r], tree[id]);
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 36908kb
input:
1 1000 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 299 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 824 1...
output:
46 1 12 2 46 1 46 1 73 1 100 1 51 1 100 1 100 1 73 1 0 73 1 73 1 73 1 73 1 73 1 19 1 51 1 73 1 73 1 73 1 44 1 51 1 51 1 73 1 22 2 73 1 46 1 0 73 1 yes 57 1 73 1 73 1 73 1 73 1 73 1 73 1 73 1 73 1 51 1 yes 73 1 51 1 73 1 30 1 73 1 73 1 15 1 73 1 73 1 73 1 73 1 46 1 73 1 65 1 0 73 1 12 1 3 1 73 1 73 1...
result:
ok 1911 tokens
Test #2:
score: 5
Accepted
time: 1ms
memory: 35100kb
input:
2 1000 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 406 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 98 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 970 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 ...
output:
62 1 93 1 62 3 93 1 62 2 65 1 93 1 93 1 93 1 93 1 93 1 62 2 1 93 1 93 1 62 2 62 2 62 3 42 1 93 1 93 1 62 2 44 1 93 1 62 2 93 1 62 1 93 1 72 1 72 1 62 1 72 1 23 1 72 1 no 62 2 72 1 72 1 72 1 62 3 72 1 72 1 72 1 no 43 1 72 1 62 2 40 1 62 2 8 1 62 2 62 2 0 62 2 62 1 62 1 62 1 62 2 62 2 62 1 62 2 5 62 1...
result:
ok 1915 tokens
Test #3:
score: 5
Accepted
time: 119ms
memory: 45324kb
input:
3 100000 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1...
output:
100 979 100 978 4 100 978 100 977 100 976 100 975 100 974 100 973 100 972 100 971 100 971 100 970 100 969 100 968 100 967 100 966 100 966 100 965 100 965 9 100 964 no 100 964 100 963 100 962 100 961 100 960 100 959 100 958 100 957 100 956 100 955 yes 100 954 100 954 100 953 100 952 100 951 100 950 1...
result:
ok 191356 tokens
Test #4:
score: 5
Accepted
time: 123ms
memory: 43192kb
input:
4 100000 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1...
output:
100 979 100 978 100 977 100 976 100 975 100 974 100 974 100 973 no 100 972 100 971 100 970 100 970 100 969 100 968 100 967 100 966 no 100 965 100 964 100 963 100 962 100 961 100 960 100 959 100 959 0 100 958 100 957 100 957 100 957 100 956 100 955 100 954 100 953 0 100 952 2 100 951 100 950 100 950 ...
result:
ok 191356 tokens
Test #5:
score: 5
Accepted
time: 98ms
memory: 41056kb
input:
5 100000 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3...
output:
30 3312 30 1774 30 3311 30 2286 0 30 365 30 3310 30 3309 30 3308 30 3307 30 3306 30 3305 30 1856 30 387 30 1033 30 3304 30 1681 30 3303 30 3302 30 3302 30 3301 30 3300 30 845 30 544 30 2719 30 3299 30 1344 30 3298 30 3298 yes 30 3297 30 3296 30 3295 30 473 30 3294 30 3293 30 3292 yes 30 859 30 3291 ...
result:
ok 191359 tokens
Test #6:
score: 5
Accepted
time: 95ms
memory: 44088kb
input:
6 100000 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2...
output:
30 33114 30 12379 30 33114 30 33104 30 23307 30 33094 30 33084 30 1497 no 30 33074 30 13431 30 33064 30 19 30 33054 30 33044 30 4288 30 10728 30 33034 30 6847 30 33024 30 10621 30 33014 30 10308 1 30 11959 30 3935 30 19153 30 33004 30 32994 30 2789 30 32984 30 32984 0 30 21909 30 32984 30 10889 30 3...
result:
ok 191357 tokens
Test #7:
score: 5
Accepted
time: 75ms
memory: 54312kb
input:
7 100000 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1 0 1 4 1 5 1 12 2 7 3 4 4 0 0 1 0 1 3 2 2 2 1 3 0 3 2 3 2 7 0 2 1 1 3 78193 0 5 2 8 7 10 4 4 2 1 0 0 1 1 9 0 1 2 1 7 10 0 0 0 6 0 0 4 7 4 3 1 2 0 0 1 12 2 0 2 5 3 1 0 3 4 7 1 0 9 4 1 5 2 6 23 0 12 6 6 0 2 8 4 2 5 2 1 0 3 10 8 0 2 5 1 2 6 5 9 1 0 0 9 4 3 0 5 0 0 6 4 4 0 1 3 13 0 2 4 1 5 2 0 5 4 2 1 ...
result:
ok 100000 tokens
Test #8:
score: 5
Accepted
time: 64ms
memory: 53364kb
input:
8 100000 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 8 5 2 0 8 4 8 1 2 0 2 0 1 9 1 0 0 0 2 2 0 0 3 0 4 3 1 5 1 5 2 3 11 8 2 3 3 6 2 0 3 0 1 1 1 3 1 0 16 8 0 0 8 13 4 0 3 0 3 0 0 0 0 0 4 7 2 0 2 8 10 0 0 0 4 0 8 2 0 0 7 1 3 5 9 1 0 2 4 0 8 0 3 2 4 1 3 0 0 1 1 5 8 1 0 0 2 4 2 0 3 0 1 3 0 2 0 1 2 15 0 5 2 13 0 3 0 0 0 1 1 3 4 1 1 2 0 4 2 2 14 1 4 5 9 0...
result:
ok 100000 tokens
Test #9:
score: 5
Accepted
time: 94ms
memory: 53432kb
input:
9 100000 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 1 1 1 1 1 3 1 3 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1...
output:
no no no no no no no no no no no yes no no no no no no no no no no no yes no no yes no no no no no no no no no no no no yes no no yes yes no no no no no no no no no no no no no yes no no no no no no no no no no no yes no no yes no no no no no no no no no no no no yes no no yes yes no no no no no no ...
result:
ok 100000 tokens
Test #10:
score: 5
Accepted
time: 85ms
memory: 54104kb
input:
10 100000 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 ...
output:
no no no no no no no no no no no no no no no yes yes no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no no no no no no yes yes no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no ...
result:
ok 100000 tokens
Test #11:
score: 5
Accepted
time: 122ms
memory: 53780kb
input:
11 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 ...
output:
76221 1 50830 1 72471 1 72471 1 54048 1 54048 1 54048 1 22048 1 16493 1 47298 1 50708 1 26958 1 38307 1 33000 1 no 33000 1 33000 1 33000 1 14143 1 33000 1 23657 1 12221 1 no 12093 1 12221 1 12157 1 12208 1 12221 1 12073 1 12221 1 12221 1 2 12221 1 5907 1 12221 1 11458 1 12221 1 12221 1 11073 1 12208...
result:
ok 191357 tokens
Test #12:
score: 5
Accepted
time: 129ms
memory: 53404kb
input:
12 100000 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 ...
output:
64431 1 61681 1 2343 1 3 43431 1 43431 1 43431 1 34516 1 13424 1 43431 1 43431 1 43431 1 21116 1 15931 1 9601 1 43431 1 14281 1 34223 1 34223 1 34223 1 28030 1 28030 1 22280 1 22280 1 18969 1 12780 1 3 15719 1 15719 1 14280 1 9181 1 1767 1 3128 1 14280 1 15719 1 12455 1 14280 1 15719 1 12530 1 15719...
result:
ok 191360 tokens
Test #13:
score: 5
Accepted
time: 120ms
memory: 53936kb
input:
13 100000 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 ...
output:
46658 1 52000 1 yes 17323 1 47823 1 47823 1 41266 1 14143 1 41266 1 27407 1 27407 1 no 13016 1 27407 1 18907 1 15987 1 19753 1 12073 1 19954 1 19954 1 4 19954 1 5907 1 19611 1 15987 1 19954 1 19954 1 15954 1 19954 1 8 14861 1 13 7407 1 4664 1 5959 1 19954 1 17204 1 2343 1 1 17204 1 14861 1 14477 1 1...
result:
ok 191356 tokens
Test #14:
score: 5
Accepted
time: 131ms
memory: 53412kb
input:
14 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 ...
output:
70250 1 28488 1 24024 1 9601 1 40253 1 14281 1 29750 1 25473 1 28738 1 29750 1 29750 1 29750 1 29750 1 29750 1 12780 1 0 29738 1 19344 1 14753 1 12297 1 2253 1 5378 1 14280 1 19344 1 12455 1 14280 1 19344 1 12530 1 19344 1 14753 1 19344 1 19344 1 8738 1 14753 1 19344 1 14753 1 19344 1 no 9323 1 1934...
result:
ok 191360 tokens
Test #15:
score: 5
Accepted
time: 133ms
memory: 54580kb
input:
15 100000 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...
output:
no 26093 1 71500 1 19840 1 39524 1 41208 1 13823 1 71500 1 55111 1 1 47611 1 6840 1 35861 1 25622 1 47611 1 24860 1 15954 1 24860 1 2 24860 1 0 8340 1 7664 1 5959 1 24860 1 24860 1 2343 1 7 24860 1 24860 1 24860 1 19516 1 9610 1 24860 1 24860 1 24860 1 10204 1 12360 1 9601 1 24860 1 11281 1 24860 1 ...
result:
ok 191357 tokens
Test #16:
score: 5
Accepted
time: 129ms
memory: 54032kb
input:
16 100000 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 ...
output:
73250 1 73250 1 65250 1 17300 1 5 46378 1 46378 1 39293 1 15297 1 2253 1 5378 1 22245 1 46378 1 12455 1 32398 1 46378 1 26208 1 37676 1 37676 1 37676 1 37676 1 7675 1 37676 1 33926 1 33926 1 24426 1 no 9323 1 24426 1 19344 1 19344 1 7142 1 19344 1 19344 1 19344 1 no 6343 1 19344 1 10844 1 15987 1 15...
result:
ok 191358 tokens
Test #17:
score: 5
Accepted
time: 130ms
memory: 53700kb
input:
17 100000 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 ...
output:
14991 1 14991 1 0 14991 1 14991 1 14991 1 14991 1 9321 1 14991 1 85 1 14991 1 14991 1 3389 1 14991 1 14991 1 8171 1 14991 1 14991 1 14991 1 7300 1 1 14991 1 3241 1 14991 1 14991 1 14991 1 3078 1 14991 1 14991 1 1 14991 1 14991 1 8171 1 13776 1 2319 1 no 11969 1 11156 1 11969 1 8324 1 8324 1 8324 1 y...
result:
ok 191357 tokens
Test #18:
score: 5
Accepted
time: 144ms
memory: 56344kb
input:
18 100000 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 ...
output:
6664 1 10003 376 10003 376 10003 91 10003 91 1 10003 91 0 10003 91 4612 1 2737 1 10003 91 10003 91 2411 1 0 8229 1 8229 1 8229 1 7466 1 8229 1 7466 1 7466 1 7466 1 7466 1 5884 1 6935 1 7466 1 7125 1 7466 1 7466 1 7466 1 7466 1 7466 1 7125 1 7125 1 7125 1 7125 1 2156 7125 1 7125 1 7125 1 3133 1 1693 ...
result:
ok 191358 tokens
Test #19:
score: 5
Accepted
time: 152ms
memory: 58764kb
input:
19 100000 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 ...
output:
5837 1 7018 1 6352 1 7018 1 6352 1 7018 1 1 7018 1 7018 1 7018 1 7018 1 7018 1 5837 1 5837 1 7018 1 6549 1 5837 1 5565 1 5837 1 4716 1 7018 1 5074 1 7018 1 4979 1 1478 6948 1 no 4716 1 6948 1 6948 1 6726 1 6948 1 5837 1 5837 1 5837 1 5837 1 4076 1 no 5837 1 5837 1 5837 1 85 1 5837 1 5837 1 4288 1 49...
result:
ok 191356 tokens
Test #20:
score: 5
Accepted
time: 139ms
memory: 58300kb
input:
20 100000 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 ...
output:
1608 1 no 10002 1 4364 1 8329 1 10002 1 8329 1 10002 1 no 2957 1 10002 1 10002 1 10002 1 6406 1 10002 1 10002 1 10002 1 no 5719 1 10002 1 6406 1 6406 1 5719 1 3748 1 10002 1 10002 1 0 10002 1 3316 1 5719 1 5719 1 10002 1 10002 1 6162 1 10002 1 0 5719 1 0 4726 1 2804 1 2895 1 10002 1 10002 1 1223 1 1...
result:
ok 191355 tokens
Extra Test:
score: 0
Extra Test Passed