QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#47187#1859. Reasonable Workplace RelationshipYaoBIG#AC ✓354ms63068kbC++2.6kb2022-09-04 17:13:162022-09-04 17:13:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-04 17:13:18]
  • 评测
  • 测评结果:AC
  • 用时:354ms
  • 内存:63068kb
  • [2022-09-04 17:13:16]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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