QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626451 | #7311. Welcome to ICPCCamp 2017 | ucup-team4906# | WA | 34ms | 7888kb | C++20 | 2.1kb | 2024-10-10 09:10:48 | 2024-10-10 09:10:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define N 200010
const int mod = int(1e9 + 7);
int n, m;
vector<int>vi[N];
int c[N];
int vst[N], p[N], q[N];
int num[N];
int P[N];
int qry(int x) {int s = 0; for(;x;x -= x & (-x))s = (s + c[x]) % mod; return s;}
void add(int x, int w) {for(;x <= m + 1; x += x & (-x))c[x] = (c[x] + w) % mod;}
void sol()
{
// cout << "??:" << n << ' ' << m << '\n';
for (int i = 1; i <= m; i ++) vst[i] = -1;
for (int i = 1; i <= n; i ++)
{
int k; cin >> k;
while (k --)
{
int x;
cin >> x;
vi[i].push_back(x);
}
}
for (int i = 1; i <= m; i ++) cin >> p[i];
for (int i = 1; i <= m; i ++) q[p[i]] = i;
P[0] = 1;
for (int i = 1; i <= m; i ++) P[i] = (P[i - 1] + P[i - 1]) % mod;
set<int>S;
for (int i = 1; i <= n; i ++)S.insert(i);
int sum = 0, ans = 0;
for (int t = 0;; t ++)
{
if (S.empty()) break;
vector<int>era;
for (int i : S)
{
if (vi[i].size() <= t)era.push_back(i);
else
{
int x = vi[i][t];
if (vst[x] == -1) vst[x] = t;
}
}
for (int x : era) S.erase(x);
}
for (int i = 1; i <= m; i ++) if (vst[i] == -1)vst[i] = m + 1;
for (int i = m; i >= 1; i --)
{
int x = p[i]; int j = vst[x] + 1;
// cout << "??:" << x << ' ' << j << " " << qry(j) << endl;
ans = (ans + (qry(j) + 1)) % mod;
if (j <= m)
{
add(j, (mod - P[num[j]] + 1) % mod);
num[j] ++;
add(j, (P[num[j]] + mod - 1) % mod);
}
}
ans = (ans + 1) % mod;
cout << ans << '\n';
for (int i = 1; i <= n; i ++) vi[i].clear();
for (int i = 1; i <= m + 1; i ++) vst[i] = -1, c[i] = num[i] = 0;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int T = 1;
// cin >> T;
while (cin >> n >> m) sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7888kb
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: 34ms
memory: 5632kb
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:
62 570 275 17 17 4658 38 49 964 123 37 69 2 4 32 26 15 133 42 26 47 19 3 35 32 2 4 24 33 13 2 36 4 97 20 41 2 22 35 32 22 24 10 21 31 187 39 5 18 17 90 64 16 18 57 6 37 79 64 56 61 7 64 38 32 26 7 16 78 4 13 13 34 9 68 11 8 95 124 87 4 2 34 4 35 13 8 128 79 23 59 37 27 9 149 84 8 13 152 8 32 36 16 6...
result:
wrong answer 10th numbers differ - expected: '208', found: '123'