fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. unsigned long long t, o;
  4. unsigned long long m, q;
  5. struct node
  6. {
  7. 	unsigned long long a, b;
  8. };
  9. vector <node> e;
  10. unsigned long long calc(unsigned long long x)
  11. {
  12. 	if (x == 0)
  13. 		return 0;
  14. 	if (x % 2 == 0)
  15. 		return x / 2 * (x - 1);
  16. 	else
  17. 		return (x - 1) / 2 * x;
  18. }
  19. void work()
  20. {
  21. 	cin >> m >> q;
  22. 	for (unsigned long long i = 1; i <= m; i++)
  23. 	{
  24. 		unsigned long long a, b;
  25. 		cin >> a >> b;
  26. 		node ts = {a, b};
  27. 		if (i == 1)
  28. 		{
  29. 			e.push_back(ts);
  30. 		}
  31. 		else if (a == e.back().a)
  32. 		{
  33. 			e.back().b = min(e.back().b, b);
  34. 		}
  35. 		else if (b < a / e.back().a * e.back().b)
  36. 		{
  37. 			e.push_back(ts);
  38. 		}
  39. 	}
  40. 	for (unsigned long long i = 1; i <= q; i++)
  41. 	{
  42. 		unsigned long long up;
  43. 		cin >> up;
  44. 		unsigned long long ans = calc(up) * e[0].b;
  45. 		for (unsigned long long i = 1; i < e.size(); i++)
  46. 		{
  47. 			// cout << ans << " ";
  48. 			unsigned long long parts = up / e[i].a;
  49. 			unsigned long long ts = calc(parts) * e[i].a;
  50. 			ts += (up - parts * e[i].a) * parts;
  51. 			ans += ts * (e[i].b - e[i].a / e[i - 1].a * e[i - 1].b);
  52. 		}
  53. 		cout << ans << endl;
  54. 	}
  55. 	e.clear();
  56. 	return ;
  57. }
  58. int main()
  59. {
  60. 	freopen("paradise.in", "r", stdin);
  61. 	freopen("paradise.out", "w", stdout);
  62. 	cin >> t >> o;
  63. 	while (t--)
  64. 	{
  65. 		work();
  66. 	}
  67. 	return 0;
  68. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
10 0
20 9
1 29476947032
6 112467782375
12 131337117983
48 525348471932
144 1535696730495
288 2843096643187
576 5263917712555
1152 8994725088102
3456 14248772167783
10368 38305879730216
20736 63369455262902
62208 66734431123746
124416 102259099697705
248832 180183230453043
746496 499789926325999
2239488 1268706222239493
4478976 2173639219928800
8957952 3227267205131250
26873856 5188509546417526
80621568 15562036842856060
66
23
1
44
2
44
14
1
90
20 9
1 23884386676494852
1 30756334008105249
1 21279924463638329
1 34925170350423221
1 22983162276727887
1 19386708773874566
1 18664826517990392
3 89998446482337168
3 45671848366690297
9 137015545100070891
9 140409522458478244
9 271962891664406939
9 139111068347676178
45 529545107169829411
45 477268807789482386
45 800270226176994373
90 924286209725681816
90 925254823215857109
180 998323481171431680
180 999133603812597084
8
38
24
47
17
97
92
31
43
20 10
1 65188929797130764
1 32820918778902992
1 46027506457747036
1 39177504966099618
3 90262811137131858
3 77069806303656370
3 93388682991137380
3 94025790289580520
3 94745344749034713
12 217562218843351935
12 227039748588632409
12 119272079160464602
12 132846533543842903
12 236321825778118243
12 130123536291796960
72 806304864358086158
72 648911317722152547
72 833491727687050654
72 750771583495753362
144 999089923536995584
68
98
14
92
0
58
33
34
75
63
19 10
1 27594128660618541
1 36646951838363653
5 252101612000122592
5 185989891789386066
5 198621188736340802
5 249052486901933809
5 134425953670783094
15 397536881187162734
15 415577463441668327
75 999603098373678336
75 999846813925988424
75 999771505552453164
75 999663776094038910
75 999618335799489622
150 999960122011352757
150 999891372349647872
150 999937565840376922
150 999970546737130316
150 999955274085180101
58
48
16
95
98
98
86
48
37
40
20 9
1 44473105481579114
1 32019875199061872
1 40655391626152999
1 23526045448015902
3 86462677249680789
3 70271680409540888
6 196010822468272637
6 213116520431757563
6 140393673297635312
6 167201691263672709
6 165565444221110303
12 280748714420066496
24 560760381648435520
24 841412315576416932
48 999457967151712921
48 999126415286102656
96 999121270702060931
96 999577447095993882
96 998949743449754496
192 999814715686454528
34
28
76
32
63
23
84
87
1
19 10
1 86771586105877536
1 73129583056420293
1 46399822648230013
2 88934395319533090
2 99819971178023098
2 127250958812595626
2 97078618028860919
2 169434893750480059
8 344381176133761223
8 346627414019767059
8 625131439145140426
8 501002899290897545
40 999709957069894498
40 998902858822360576
80 999880257845870156
80 999921850411146076
80 999933033148184592
80 999870235970145280
80 999964056240643789
88
79
79
64
15
87
60
32
46
95
20 10
1 16831522591
2 33596536697
10 167553292911
20 334930555162
40 669088693434
120 2006380954656
360 5975169367358
720 11947117680101
1440 23890313664258
2880 47760248608651
20160 334234616935897
40320 667935665347468
161280 2668168345269220
645120 10667364054676632
1290240 21287794823231912
2580480 42566680631408096
12902400 212638499365352896
38707200 637637625494690944
116121600 999756739898928512
232243200 998976158987725568
23
71
80
11
76
96
66
41
66
51
20 10
1 250463122794261763
1 342055722862419078
1 317086669378505438
1 281425329351416663
1 211343701021732465
2 612654603893908699
2 533377919131422675
2 653199750059727848
2 585304429322870128
2 344957582619134094
2 518352050033021783
4 628492771584613032
4 735838500699624951
4 955600795544323051
4 879676487426999815
4 720212640810745590
16 999966063698805107
16 999931025709179904
16 999986831151328518
16 999934042441225165
25
88
30
69
11
98
54
66
64
3
19 8
1 99443552626
2 182065954098
4 364131908196
8 687078272593
16 1242593363710
32 2183243243915
64 2934501089490
128 4287282367829
640 17072257198877
640 27703818183504
3200 76944265995785
6400 151066968203533
19200 426728518956023
96000 1689813159066119
384000 2624530890192747
768000 5249061780385494
2304000 14335569106636576
11520000 61218285811872027
23040000 86332670074577843
90
7
89
5
37
50
87
11
20 8
1 4340044163
2 8680049153
16 69414321329
64 277410800832
128 553302090362
256 1105833527570
2048 8833388045868
4096 17619322407699
16384 70384180999303
32768 140742551799043
65536 281252133496806
131072 562461014419426
262144 1124439613457484
1048576 4488366826385048
8388608 35892613295196908
16777216 71781505734332304
33554432 143562230874931392
67108864 286780489138465536
268435456 999475236640198400
1073741824 999518830591671424
68
100
45
52
52
40
34
95
stdout
copy 
Standard output is empty
https://ideone.com/1BEMXG
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!