#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) ((int)v.size())
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define pb push_back
#define pry puts("YES")
#define prn puts("NO")
#define endl '\n'
#define fst first
#define scn second
struct node{
int sb, se;
int fb;
};
vector<node> ns;
struct SGT {
int n;
vector<int> t;
void
init(int _n)
{
n = _n;
t.resize(4*n, 0);
}
void
update(int i, int l, int r, int tl, int tr)
{
if (tr < l || r < tl)
return;
if (tl <= l && r <= tr) {
t[i] = 1;
return;
}
if (l == r)
return;
int mid = (l + r) >> 1;
update(i>>1, l, mid, tl, tr);
update(i>>1|1, mid+1, r, tl, tr);
return;
}
void
update(int l, int r)
{
update(0, 0, n-1, max(l,0), min(r,n-1));
return;
}
int
query(int i, int l, int r, int x)
{
int ans = 0;
if (l > x || r < x)
return 0;
if (l <= x && r >= x) {
ans = t[i];
}
if (l == r)
return ans;
int mid = (l + r) >> 1;
ans += query(i>>1, l, mid, x);
ans += query(i>>1|1, mid+1, r, x);
return ans;
}
int
query(int x)
{
return query(0, 0,n-1,x);
}
};
int
minimumInstructions(int n, int m, int k, vector<int> c,
vector<int> a, vector<vector<int>> b)
{
vector<int> has[k];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < a[i]; ++j) {
has[b[i][j]].pb(i);
}
}
ns.resize(m+n);
for (int i = 0; i < n+m; ++i) {
ns[i].sb = -2;
ns[i].se = -2;
ns[i].fb = -1;
}
SGT tr;
tr.init(n);
for (int i = m; i < n+m; ++i) {
for (int u : has[c[i-m]]) {
if (i - u > -1) {
if (ns[i-u].se + 1 == u) {
++ns[i-u].se;
} else {
ns[i-u].se = u;
ns[i-u].sb = u;
}
}
if (i - u - m > -1) {
if (ns[i-u-m].fb == u - 1)
ns[i-u-m].fb = u;
}
}
}
for (int i = 0; i < n+m; ++i) {
if (ns[i].sb == 0 && ns[i].se == n-1 && i >= m) {
tr.update(i-m,i-m);
}
if (ns[i].se != m-1 || ns[i].fb < 0)
continue;
if (ns[i].sb > ns[i].fb + 1)
continue;
/* cout << i-m << ' ' << ns[i].sb << ' ' << ns[i].se << ' ' << ns[i].fb << endl; */
if (i -m + ns[i].fb + 1 >= 0)
tr.update(i - m + ns[i].sb, i + ns[i].fb +1 - m);
}
/* for (int i = 0; i < n; ++i) { */
/* cout << tr.query(i) << ' '; */
/* } */
/* cout <<endl; */
if (!tr.query(0))
return -1;
int r = m-1;
int l = 0;
int ans = 1;
bool t = 1;
while (t) {
t = 0;
/* cout << l << ' ' << r << endl; */
for (int i = min(r,n-m); i > l; --i) {
if (tr.query(i)) {
t = 1;
l = i;
r = i + m;
++ans;
if (i + m - 1 >= n-1)
return ans;
}
}
}
return -1;
}
#ifdef ONPC
void
solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<vector<int>> b(m);
for (int i = 0; i < m; ++i) {
b[i].resize(a[i]);
for (int j = 0; j < a[i]; ++j) {
cin >> b[i][j];
}
}
cout << minimumInstructions(n, m, k, c, a, b) << endl;
}
int32_t
main()
{
freopen("in", "r", stdin);
int t = 1;
cin >> t;
while(t--)
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
