QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317130#7311. Welcome to ICPCCamp 2017ckiseki#WA 28ms3624kbC++202.6kb2024-01-28 15:56:262024-01-28 15:56:26

Judging History

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

  • [2024-01-28 15:56:26]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3624kb
  • [2024-01-28 15:56:26]
  • 提交

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'