QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626451#7311. Welcome to ICPCCamp 2017ucup-team4906#WA 34ms7888kbC++202.1kb2024-10-10 09:10:482024-10-10 09:10:48

Judging History

你现在查看的是最新测评结果

  • [2024-10-10 09:10:48]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:7888kb
  • [2024-10-10 09:10:48]
  • 提交

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;
}

詳細信息

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'