QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317130 | #7311. Welcome to ICPCCamp 2017 | ckiseki# | WA | 28ms | 3624kb | C++20 | 2.6kb | 2024-01-28 15:56:26 | 2024-01-28 15:56:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
using lld = int64_t;
const int mod = 1000000007;
int add(int a, int b) {
assert(0 <= a and a < mod);
assert(0 <= b and b < mod);
return a + b >= mod ? a + b - mod : a + b;
}
int mul(lld a, lld b) {
assert(0 <= a and a < mod);
assert(0 <= b and b < mod);
return static_cast<int>(a * b % mod);
}
struct Segtree {
int n;
vector<int> st;
Segtree(int _n) : n(_n), st(n * 2) {}
void set(int p, int v) {
for (st[p += n] = v; p >>= 1; )
st[p] = add(st[p << 1], st[p << 1 | 1]);
}
int query(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = add(res, st[l++]);
if (r & 1) res = add(res, st[--r]);
}
return res;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
vector<int> best(m, m);
for (int i = 0; i < n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
--x;
best[x] = min(best[x], j);
}
}
vector<int> r(m);
for (int i = 0; i < m; i++)
cin >> r[i], --r[i];
int ans = 1;
vector<int> cnt(m), way(m + 1);
way[0] = 0;
for (int i = 1; i <= m; i++)
way[i] = add(add(way[i], way[i]), 1);
orange(all(way));
for (int i = 0; i < m; i++)
if (best[i] < m)
++cnt[best[i]];
Segtree sgt(m);
for (int i = 0; i < m; i++)
sgt.set(i, way[cnt[i]]);
for (int i = 0; i < m; i++) {
// r[i] is not in the set
// r[0..i-1] is in the set
int b = best[r[i]];
if (b < m) {
--cnt[b];
sgt.set(b, way[cnt[b]]);
int q = sgt.query(0, b + 1);
debug(q, "case 1");
ans = add(ans, q);
} else {
int q = sgt.query(0, m);
debug(q, "case 2");
ans = add(ans, q);
}
ans = add(ans, 1);
}
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3588kb
input:
2 3 2 1 3 3 2 1 3 2 1 3 0 3 1 2 3
output:
5 4
result:
ok 2 number(s): "5 4"
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 3624kb
input:
3 16 1 7 1 16 1 4 14 10 8 1 4 13 5 9 7 12 2 6 3 16 11 15 10 16 2 10 6 2 12 1 3 16 4 1 2 11 5 1 14 1 9 4 14 10 4 13 2 7 14 1 15 1 14 6 15 12 9 5 14 10 16 4 7 11 2 3 8 1 13 6 15 2 15 5 2 10 13 1 11 2 6 10 3 4 9 12 3 13 1 10 7 3 4 1 10 12 13 6 9 14 15 11 5 2 8 5 6 1 6 1 6 1 4 5 4 5 1 2 3 3 4 6 3 3 5 4 ...
output:
30 36 35 13 9 162 38 37 104 38 37 63 2 4 10 26 15 73 34 26 60 19 4 35 32 2 4 12 33 13 2 18 4 17 20 41 2 22 33 10 22 24 8 21 31 187 39 5 18 9 90 64 39 18 57 6 37 79 12 56 61 7 12 38 32 26 7 8 22 4 11 13 34 16 68 12 6 95 120 87 4 2 34 4 35 13 6 14 79 23 59 27 27 9 39 84 6 11 32 6 10 36 8 26 15 4 78 8 ...
result:
wrong answer 1st numbers differ - expected: '62', found: '30'