QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317138 | #7311. Welcome to ICPCCamp 2017 | ckiseki# | AC ✓ | 44ms | 7980kb | C++20 | 2.6kb | 2024-01-28 16:20:58 | 2024-01-28 16:20:58 |
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 = 1'000'000'007;
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 - 1], way[i - 1]), 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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
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: 0
Accepted
time: 28ms
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:
62 570 275 17 17 4658 38 49 964 208 37 69 2 4 32 26 15 133 42 26 68 19 4 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 39 18 57 6 37 79 64 56 61 7 64 38 32 26 7 16 78 4 13 13 34 16 68 12 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 ...
result:
ok 20000 numbers
Test #3:
score: 0
Accepted
time: 26ms
memory: 3720kb
input:
7 43 2 20 8 1 28 2 26 42 2 32 27 1 1 1 24 1 5 2 27 9 19 25 31 33 21 26 30 5 38 39 18 29 28 22 11 40 15 35 13 23 24 4 17 34 16 7 36 1 41 3 43 12 32 20 14 37 6 8 10 42 25 7 1 5 1 1 1 1 1 1 1 4 1 3 3 2 3 7 2 5 3 1 1 1 7 1 5 2 1 4 1 3 1 6 3 7 1 6 1 3 3 3 7 2 1 1 1 5 2 4 5 2 7 6 2 6 4 1 4 1 7 3 6 3 2 7 6...
output:
1631 128 662023095 811 1220558 12237484 157 23 423317 533 6144 446 16 92 464 66 3717 335 269 143 1149 8 87 462 8 146 273 60 2750 3121 25730 8300 453 71 8 225 179 1024 2133 80 1869 210 5 520 145 6406 397 448 2 5385 374 2 1568 1340 625 2109 1906 15 134293 207 452 2 534 207 338 747 141 834 8183 396 613...
result:
ok 5000 numbers
Test #4:
score: 0
Accepted
time: 28ms
memory: 3828kb
input:
332 114 1 56 1 49 1 61 2 104 103 1 21 1 80 2 48 9 4 22 60 54 76 3 40 1 91 1 41 1 33 1 16 1 24 1 110 2 81 54 1 85 2 87 83 1 39 1 37 1 80 2 76 30 2 77 106 1 21 2 65 32 1 58 1 49 1 39 2 100 22 1 102 2 88 30 1 105 1 113 2 72 99 4 11 28 90 68 2 100 70 4 106 69 33 37 1 43 2 64 54 2 87 72 2 106 114 2 106 6...
output:
883483423 376235721 57578466 745793211 322521185 896987515 307265211 625207906 69260834 10142 728040081 637898435 647006134 388201470 154859 657704184 481217084 201985264 708777 793575511 777386063 1123 454 765604361 149499192 827505894 31907427 3786811 23077 868980658 310604661 7833224 50863221 217...
result:
ok 500 numbers
Test #5:
score: 0
Accepted
time: 31ms
memory: 3900kb
input:
621 2007 1 1465 1 1362 1 1493 2 628 1345 1 1446 1 985 1 1179 2 384 1567 1 1076 2 1234 321 1 543 1 1847 3 282 1492 1563 1 787 1 1027 1 242 2 1094 514 2 860 1041 2 1853 1191 2 912 452 4 1312 834 1059 486 1 1192 1 329 1 1503 3 1793 1882 1580 2 444 1749 1 1151 2 938 1059 2 399 1064 1 385 2 871 1190 2 13...
output:
434218100 843108075 900298261 176519701 72793001 855849581 227252458 198516093 134099126 908583582 49833642 174002989 103644691 715492397 485920845 145586002 49642063 648694435 488579377 73382381 389591312 423770169 493768501 386823481 760789999 45124599 347280587 127580523 4364 467535190 830713404 ...
result:
ok 50 numbers
Test #6:
score: 0
Accepted
time: 39ms
memory: 7980kb
input:
126405 200000 1 181938 2 56300 7338 1 101988 2 8883 136306 1 98423 1 76781 1 31908 1 49420 2 114001 32260 1 149532 1 147565 2 174485 110547 2 33937 60001 1 138807 1 129263 3 95277 116816 159765 1 93820 1 119526 2 176428 158503 2 109228 74534 1 145027 2 50256 163731 1 196627 2 150778 173871 1 177984 ...
output:
661326989
result:
ok 1 number(s): "661326989"
Test #7:
score: 0
Accepted
time: 41ms
memory: 7968kb
input:
32764 200000 4 32669 2034 137677 157374 1 120487 19 90939 147780 195220 143751 79105 72149 54500 23013 17141 9172 172475 45866 126229 77692 75672 70812 47786 180432 122613 17 178624 103070 182049 51065 105374 31234 15188 93118 164080 21460 30935 151825 46711 152525 175812 32597 180538 3 138911 28081...
output:
885398592
result:
ok 1 number(s): "885398592"
Test #8:
score: 0
Accepted
time: 38ms
memory: 7804kb
input:
17234 200000 3 152748 130305 18708 20 107564 90964 96824 105786 132889 111245 5908 127664 16333 137438 186144 171482 150527 172709 151007 156991 171865 43636 82060 197008 6 190295 48278 86033 93148 5431 18077 7 42183 85071 14314 83272 164967 190587 140044 8 135789 172485 96645 68432 53983 159752 188...
output:
35359153
result:
ok 1 number(s): "35359153"
Test #9:
score: 0
Accepted
time: 40ms
memory: 7844kb
input:
2686 200000 3 34905 106578 123527 24 197549 151584 57127 52102 138903 83267 194979 49629 29897 2005 184951 28348 119372 47746 36186 54079 178911 100829 158578 165713 191081 175518 103586 146210 113 137937 137689 158028 28506 58619 127513 17384 166089 164564 117519 193809 105076 81123 22337 53875 793...
output:
266652290
result:
ok 1 number(s): "266652290"
Test #10:
score: 0
Accepted
time: 37ms
memory: 7948kb
input:
369 200000 30 180553 17474 132462 64502 35446 190112 46372 98267 40928 107615 159636 170883 84846 108520 27238 51577 150692 185368 85599 33459 99609 140902 21867 145420 196243 27664 78345 135923 19159 31023 97 53152 102912 29197 130411 141629 24584 106082 114440 86121 41665 132713 121142 107047 1504...
output:
351500019
result:
ok 1 number(s): "351500019"
Test #11:
score: 0
Accepted
time: 44ms
memory: 7804kb
input:
11 200000 895 61784 78254 48407 195251 33463 139947 188001 158222 62008 104908 2112 175239 138856 165697 191089 14887 19276 63301 30908 118378 193617 142702 44334 157185 55461 7100 189771 8291 66241 131628 125805 29784 164895 8624 42578 36178 67912 51140 95357 144704 3308 26 153020 158466 20404 1235...
output:
616668026
result:
ok 1 number(s): "616668026"
Extra Test:
score: 0
Extra Test Passed