QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317127 | #7311. Welcome to ICPCCamp 2017 | ckiseki# | WA | 27ms | 3604kb | C++20 | 2.6kb | 2024-01-28 15:52:28 | 2024-01-28 15:52:29 |
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[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: 0ms
memory: 3576kb
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: 27ms
memory: 3604kb
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:
21 30 33 17 7 171 44 54 101 45 37 79 2 5 8 37 24 88 50 43 81 35 4 43 32 2 3 14 55 16 2 26 3 16 37 55 2 24 58 6 37 37 6 41 31 331 39 5 40 7 113 116 41 28 132 5 54 142 7 117 79 13 9 97 53 56 8 5 24 3 13 13 44 20 109 20 6 182 214 125 3 2 50 5 58 22 4 8 135 35 59 43 32 14 61 118 4 9 50 4 6 98 5 32 22 3 ...
result:
wrong answer 1st numbers differ - expected: '62', found: '21'