QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#47187 | #1859. Reasonable Workplace Relationship | YaoBIG# | AC ✓ | 354ms | 63068kb | C++ | 2.6kb | 2022-09-04 17:13:16 | 2022-09-04 17:13:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class Fenwick {
private:
vector<ll> val;
public:
Fenwick(int n) : val(n+1, 0) {}
// Adds v to index i
void add(int i, ll v) {
for (++i; i < val.size(); i += i & -i) {
val[i] += v;
}
}
// Calculates prefix sum up to index i
ll get(int i) {
ll res = 0;
for (++i; i > 0; i -= i & -i) {
res += val[i];
}
return res;
}
ll get(int a, int b) { return get(b) - get(a-1); }
// Assuming prefix sums are non-decreasing, finds last i s.t. get(i) <= v
int search(ll v) {
int res = 0;
for (int h = 1<<30; h; h >>= 1) {
if ((res | h) < val.size() && val[res | h] <= v) {
res |= h;
v -= val[res];
}
}
return res - 1;
}
};
const ll MOD = (ll)1e9 + 7;
ll modPow(ll a, ll b) {
if (b & 1) return modPow(a, b ^ 1) * a % MOD;
if (b == 0) return 1;
return modPow(a*a % MOD, b >> 1);
}
void dfs(int i, int& cur, vector<int>& le, vector<int>& ri, const vector<vector<int>>& g) {
le[i] = cur;
++cur;
for (int t : g[i]) dfs(t, cur, le, ri, g);
ri[i] = cur;
}
int calc(int i, vector<ll>& res, const vector<int>& cou, const vector<vector<int>>& g) {
int siz = 1;
for (int t : g[i]) {
siz += calc(t, res, cou, g);
res[i] = (res[i] + res[t]) % MOD;
}
res[i] = (res[i] + cou[i] * modPow(siz, MOD - 2)) % MOD;
return siz;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
int r = -1;
vector<int> as(n), bs(n);
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
--p;
if (p != -1) g[p].push_back(i);
else r = i;
}
for (int i = 0; i < n; ++i) cin >> as[i];
for (int i = 0; i < n; ++i) cin >> bs[i];
int tmp = 0;
vector<int> le(n), ri(n);
dfs(r, tmp, le, ri, g);
vector<pair<int, int>> evs(2*n);
for (int i = 0; i < n; ++i) {
evs[2*i] = {as[i], -(i + 1)};
evs[2*i+1] = {as[i] + bs[i], (i + 1)};
}
sort(evs.begin(), evs.end());
Fenwick fenw(n);
vector<int> cou(n);
for (auto pr : evs) {
int i = abs(pr.second) - 1;
if (pr.second < 0) fenw.add(le[i], 1);
else cou[i] = fenw.get(le[i], ri[i] - 1);
/*
cerr << pr.first << ' ' << pr.second << ": ";
if (pr.second < 0) cerr << "add to " << le[i] << '\n';
else cerr << "get (" << le[i] << ' ' << ri[i] << "): " << fenw.get(le[i], ri[i] - 1) << '\n';
*/
}
vector<ll> res(n, 0);
calc(r, res, cou, g);
for (int qi = 0; qi < q; ++qi) {
int i;
cin >> i;
--i;
cout << res[i] << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3592kb
input:
2 2 0 1 1 10 1 1 1 2
output:
500000005 1
result:
ok 2 number(s): "500000005 1"
Test #2:
score: 0
Accepted
time: 3ms
memory: 3768kb
input:
1000 904 565 893 452 499 630 262 162 833 974 904 215 181 707 852 841 494 176 671 525 751 444 856 513 222 125 951 693 952 328 842 133 688 553 751 595 870 723 474 755 835 585 615 345 617 797 296 98 74 929 59 346 576 41 4 81 205 116 148 785 612 531 39 290 805 609 221 39 980 490 981 451 895 728 981 180 ...
output:
1 1 500000007 1 2 1 500000005 1 500000005 3 700000018 1 1 1 3 1 666666678 500000011 1 5 1 1 500000005 1 1 1 1 1 2 2 1 1 1 500000014 1 1 2 2 1 1 928571441 2 666666674 1 1 1 1 7 2 2 95069625 2 1 416666675 2 1 1 666666677 2 1 1 1 1 1 1 3 812500021 4 4 2 4 1 2 500000007 1 1 1 131955337 1 1 5 1 1 1 1 2 1...
result:
ok 904 numbers
Test #3:
score: 0
Accepted
time: 44ms
memory: 11096kb
input:
50000 49901 11975 31700 31264 5341 30119 35862 2906 32176 23191 48823 42687 25766 4240 49936 24389 8667 28871 27739 27415 38210 31898 15969 40060 37284 3469 18 19906 49027 37382 28923 35704 11759 37496 40442 14737 20232 29274 28007 30901 7637 42847 40873 1176 2068 27487 32994 42130 23082 36825 19686...
output:
1 956882294 472034315 1 500000005 240159700 1 573170774 9 679477622 285714294 1 333379527 995397168 500000018 786789902 570440655 507386897 47525225 537279948 899736629 500000005 944698903 1 904412017 1 308770268 394534856 63038655 1 437891060 763201075 1 598237625 41207820 634824270 813957895 51560...
result:
ok 49901 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
10 10 3 1 0 2 3 2 3 6 5 1 637553578 682292472 340844506 920618208 841655021 271248396 939928378 76811974 89324007 75416657 73006386 538904662 975498118 802467476 130382886 526476208 66018376 23665723 754550309 664901579 5 2 6 10 8 9 1 3 4 7
output:
2 4 2 1 1 1 833333345 833333349 1 1
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 354ms
memory: 50224kb
input:
300000 299936 12532 43114 34418 68551 85536 9523 41805 25420 52702 41346 7461 16327 33536 52902 91107 63853 24175 41958 51155 39654 36158 46066 68044 8317 2708 38074 56993 29081 72357 29322 96848 13312 71823 32280 57495 33462 161107 67460 10731 48141 9496 71534 31824 25005 82179 94287 17413 19728 33...
output:
1 172840500 853696947 545147224 1 810222068 3 498405838 586200453 954122566 6 950932906 878841908 3732086 2 145450100 30929416 97750620 1 1 109930354 678761869 543310623 347655680 1 533333345 155505287 259154618 250617218 655414494 531270261 750000009 1 411025184 769314756 264309728 794923139 823614...
result:
ok 299936 numbers
Test #6:
score: 0
Accepted
time: 223ms
memory: 28516kb
input:
200000 199986 26315 42432 26581 81143 100372 68271 55246 5644 585 46003 45703 19171 17485 93877 103423 63448 1867 1465 4575 2553 32166 8008 13909 6867 78188 26555 1611 3402 85380 24299 15128 398 17093 19462 57437 11960 164925 50073 19949 54396 32898 4835 23593 32738 8422 103837 61466 20096 20848 383...
output:
136954369 525408546 63361046 264335459 74623117 539216920 950293535 798257081 896882637 617340849 551498011 34645961 14541823 679498682 52626934 37509324 455715033 813844761 569483982 207876792 160654265 764741845 832967454 886538402 124486569 318432384 229852816 564473748 194685805 7147660 74526016...
result:
ok 199986 numbers
Test #7:
score: 0
Accepted
time: 5ms
memory: 4264kb
input:
10000 9986 240 9102 7569 8423 3252 1371 8744 4819 1470 6178 8187 6743 7197 8006 7114 4299 7325 3996 9964 1239 9487 5241 631 3026 3612 6907 8913 3376 3347 1986 9004 5182 5064 7798 2073 4424 121 2310 1686 8322 7210 9301 6899 4370 9199 9402 4901 8521 3586 7844 5190 8068 4062 1232 5575 3603 6561 863 38 ...
output:
1 666666678 1 666666674 3 1 714285726 3 1 1 666666686 3 3 916436317 1 1 1 1 3 714285726 571428582 857142870 1 1 1 1 1 1 1 1 1 379109093 1 1 380952390 1 47619054 1 1 3 333333366 1 1 333333338 1 359015501 1 1 1 1 952380965 1 523809534 1 1 1 1 1 3 941135014 666666678 3 1 7 718182242 1 1 1 1 1 1 6666666...
result:
ok 9986 numbers
Test #8:
score: 0
Accepted
time: 51ms
memory: 10224kb
input:
50000 49930 20299 2213 2528 11875 31378 26063 27565 10413 38733 495 35692 37179 5106 8455 20817 8743 5354 20399 8436 22659 12321 11286 32571 7853 45702 26009 38704 851 13781 40431 21045 21703 44024 26142 31179 49070 2066 28919 19646 21799 26549 48841 22701 9582 1249 47768 31167 40219 10487 46775 215...
output:
801660437 884573444 783467264 366524307 510988384 156709175 201094518 876626097 956545401 768027349 820467758 755408091 345963021 44749729 473780127 897919462 873717302 453852234 63813144 550536009 217420187 742745163 597057633 359033033 854993748 867667642 405599437 216987689 78960546 523420648 492...
result:
ok 49930 numbers
Test #9:
score: 0
Accepted
time: 4ms
memory: 3916kb
input:
4000 3974 814 1481 509 1675 1947 1620 2161 3220 3638 1794 3005 850 1520 694 3502 3728 1771 2818 1486 2657 1813 3648 1732 568 349 3504 308 2938 3779 1091 545 2532 1508 223 3345 1106 2197 2881 3267 1068 2532 815 3922 2282 1864 3060 120 3286 1127 78 774 1395 1213 499 176 1140 1399 2097 2895 2366 2 2052...
output:
800000010 1 1 9 4 1 512820540 1 1 1 5 1 1 4 1 2 1 1 2 1 880952393 1 1 666666674 555555576 2 1 1 11 1 500000005 1 1 2 1 1 500000005 1 1 1 2 1 666666674 500000006 500000005 1 3 1 1 1 1 666666680 2 2 1 5 2 3 1 888888904 166666675 1 3 7 700000009 1 1 1 1 1 1 333333346 3 2 666666674 1 2 3 6 166666681 1 1...
result:
ok 3974 numbers
Test #10:
score: 0
Accepted
time: 17ms
memory: 5168kb
input:
20000 19942 17624 19689 1005 12056 16974 1762 15594 17302 6641 18117 4646 3984 7226 17363 7799 13321 2074 15958 18101 19088 10491 6509 15404 1719 11990 1522 19524 9195 19377 17089 2392 18437 9143 3075 19680 17610 19158 18624 4445 5779 11896 5994 19504 12218 1662 6981 807 213 5456 5738 11007 15878 16...
output:
1 1 2 1 1 750000009 1 1 1 3 3 500000008 1 1 3 1 2 1 750000009 1 6 2 4 1 1 1 347058844 2 1 333333338 1 466666679 200000006 1 1 600000019 1 1 1 1 1 666666675 1 1 1 1 4 244250911 2 1 1 1 2 1 1 595238113 4 666666677 750000009 6 600000008 1 1 1 1 1 1 1 875000014 295454558 1 1 3 1 333333343 500000008 1 1 ...
result:
ok 19942 numbers
Test #11:
score: 0
Accepted
time: 46ms
memory: 13292kb
input:
50000 49951 11975 31700 31264 17080 23834 7485 2906 32176 23191 48823 42687 25766 4240 49936 25365 8667 40464 27739 10890 32356 11788 15969 510 37284 3469 18 1383 49027 37382 34266 35704 16840 37496 40442 18200 20232 9911 28007 30901 7637 42847 36586 11849 14507 14588 32994 42130 23082 36825 19686 2...
output:
666398508 41520501 714194606 922169948 538462114 836643537 313344324 258119514 682032176 797365690 531945335 341809664 378777571 405063122 623801149 581355463 314730483 760610840 57699087 641301939 836600826 504091781 888188667 284596189 353166323 403044667 872737895 871414986 818748868 713766061 47...
result:
ok 49951 numbers
Test #12:
score: 0
Accepted
time: 288ms
memory: 63068kb
input:
300000 300000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
241494237 506456013 603769841 323750618 804275209 21490725 944866575 126117750 791764913 314757294 291707226 988123205 91959555 955764138 78954411 578315618 24699137 387948533 390151477 391523039 1579374 428120759 792612404 479733669 695633279 650122940 207332324 913094982 987675699 422940474 845510...
result:
ok 300000 numbers
Test #13:
score: 0
Accepted
time: 233ms
memory: 26716kb
input:
300000 300000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 300000 numbers
Test #14:
score: 0
Accepted
time: 257ms
memory: 30232kb
input:
300000 300000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
666666674 666666674 1 1 3 3 1 857142870 1 3 1 1 3 3 1 333333342 333333338 952380973 666666674 1 1 428571438 1 1 1 47619165 1 3 1 1 380952390 1 3 1 1 1 3 857142878 3 523809542 1 1 1 1 1 666666674 1 1 238095246 3 1 584331922 1 3 1 212186499 1 1 3 7 28571456 1 1 380952390 3 1 1 857142870 3 485714303 1 ...
result:
ok 300000 numbers