QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212548#1974. Black Family Treevioalbert#AC ✓72ms18168kbC++173.3kb2023-10-13 17:09:282023-10-13 17:09:30

Judging History

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

  • [2023-10-13 17:09:30]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:18168kb
  • [2023-10-13 17:09:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) 24;
#endif

template<class A, class B>
ostream& operator<<(ostream &os, const pair<A, B> &p);
template<class T>
ostream& operator<<(ostream &os, const vector<T> &v);
template<class T, size_t sz>
ostream& operator<<(ostream &os, const array<T, sz> &v);

template<class A, class B>
ostream& operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ',' << p.second << ')';
}

template<class T>
ostream& operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  bool f = 0; for(auto &i : v) { if(f) os << ',';os << i; f = 1;}
  return os << '}';
}

template<class T, size_t sz>
ostream& operator<<(ostream &os, const array<T, sz> &v) {
  os << '{';
  bool f = 0; for(auto &i : v) { if(f) os << ',';os << i; f = 1;}
  return os << '}';
}

const int N = 1e5+5;
struct Segtree {
  int n = 0;
  vector<int> st;
#define lc (idx << 1)
#define rc (lc | 1)
#define mid ((l+r)>>1)
  Segtree() {}
  Segtree(int n) { init(n); }
  void init(int _n) {
    n = _n;
    st.assign(4*n, 0);
  }
  int pull(int lt, int rt) {
    return lt + rt;
  }
  void update(int idx, int l, int r, int x, int val) {
    debug(cerr << "update " << idx << ' ' << l << ' ' << r << ' ' << x << ' ' << val << '\n');
    if(l == r) {
      st[idx] = val;
      return;
    }
    if(x <= mid) update(lc, l, mid, x, val);
    else update(rc, mid+1, r, x, val);
    st[idx] = pull(st[lc], st[rc]);
  }
  void update(int i, int val) {
    debug(cerr << "update " << i << ' ' << val << '\n');
    return update(1, 1, n, i, val);
  }
  int query(int idx, int l, int r, int x, int y) {
    if(r < x || y < l) return 0;
    if(x <= l && r <= y) return st[idx];
    return pull(query(lc, l, mid, x, y),
                query(rc, mid+1, r, x, y));
  }
  int query(int l, int r) {
    debug(cerr << "query " << l << ' ' << r << '\n');
    return query(1, 1, n, l, r);
  }
  void print(int idx, int l, int r) {
    cerr << '(' << l << ',' << r << ')' << ' ' << st[idx] << '\n';
    if(l == r) return;
    print(lc, l, mid); print(rc, mid+1, r);
  }
  void print() {
    return print(1, 1, n);
  }
#undef lc
#undef rc
#undef mid
};

using pii = pair<int, int>;
#define fi first
#define se second
int n, q;
int a[N];
vector<int> adj[N];
vector<pii> queries[N];

void dfs(int u) {
  for(int v : adj[u]) {
    dfs(v);
    a[u] += a[v];
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> q;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 2; i <= n; i++) {
    int p; cin >> p;
    adj[p].push_back(i);
  }
  for(int i = 0; i < q; i++) {
    int l, r; cin >> l >> r;
    queries[l].emplace_back(r, i);
  }
  debug(cerr << vector(a+1, a+1+n) << '\n');
  dfs(1);
  debug(cerr << vector(a+1, a+1+n) << '\n');
  Segtree st(n);
  st.update(1, a[1]);
  vector<int> ans(q);
  for(int i = 1; i <= n; i++) {
    debug(st.print());
    for(auto [j, id] : queries[i]) {
      ans[id] = st.query(i, j);
    }
    debug(cerr << " ------- " << '\n');
    for(int v : adj[i]) st.update(v, a[v]);
  }
  for(int i = 0; i < q; i++)
    cout << ans[i] << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8176kb

input:

6 5
1 2 4 8 16 32
1 2 2 1 5
1 1
2 3
4 5
2 6
6 6

output:

63
14
56
62
32

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 8488kb

input:

5 25
4723 3513 2046 6286 9584
1 2 2 1
1 5
5 5
2 3
2 3
4 4
2 4
2 2
1 2
2 5
3 3
2 2
1 3
2 4
1 5
2 2
3 3
3 5
2 5
1 3
1 5
2 3
4 5
4 4
4 4
1 3

output:

26152
9584
11845
11845
6286
11845
11845
26152
21429
2046
11845
26152
11845
26152
11845
2046
17916
21429
26152
26152
11845
15870
6286
6286
26152

result:

ok 25 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 8204kb

input:

10 100
1457 936 8200 7604 1431 2726 6728 2545 3010 267
1 2 3 4 5 2 1 6 6
1 9
7 7
4 4
3 10
4 7
2 2
2 10
6 8
4 7
3 10
8 8
3 10
4 6
4 4
4 8
5 9
1 1
5 7
5 10
9 9
6 8
6 6
10 10
2 4
1 5
7 9
2 3
4 10
3 8
2 10
6 10
5 7
1 1
4 5
3 5
6 8
7 7
2 5
3 3
7 9
2 10
1 8
1 2
1 4
1 10
3 4
4 7
3 4
2 2
2 10
2 3
1 9
3 4
9 ...

output:

34904
6728
15038
32511
21766
30902
33447
15276
21766
32511
2545
32511
15038
15038
24311
16707
34904
14162
16707
3010
15276
6003
267
30902
34904
12283
30902
24311
32511
33447
15276
14162
34904
15038
23238
15276
6728
30902
23238
12283
33447
34904
34904
34904
34904
23238
21766
23238
30902
33447
30902
3...

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 8220kb

input:

20 400
3369 7577 2036 6800 9118 4011 4163 6177 7663 7722 8570 5139 5089 3187 9604 2154 9765 8074 4140 4101
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
3 4
10 16
5 12
8 10
10 11
14 16
13 13
20 20
14 14
8 15
7 19
6 6
5 13
16 16
10 19
2 3
4 15
3 5
18 18
7 16
2 16
8 13
20 20
13 13
3 18
10 10
17 20
5 7
8 8
1...

output:

107513
49706
98677
59400
24533
14945
5089
4101
3187
81385
85548
17720
98677
2154
67545
115090
105477
107513
8074
85548
115090
78198
4101
5089
107513
15963
26080
80742
17935
15963
107513
41465
11758
28234
107513
29672
105477
9765
11919
11758
51582
85548
67545
30159
3187
63450
118459
9604
98677
8570
2...

result:

ok 400 lines

Test #5:

score: 0
Accepted
time: 62ms
memory: 13788kb

input:

100000 100000
8029 7085 635 4300 6254 5928 4621 9793 9449 1053 5741 4135 7188 9600 5024 3024 9332 4417 6458 3033 4875 637 3280 3787 5535 9296 3390 4590 8158 5782 4977 8335 4453 5676 3484 9232 6052 214 5229 6335 1743 6960 9857 668 7712 6593 5491 579 553 1045 134 2072 9101 8502 9225 1930 5188 2631 864...

output:

2875897
4245113
7279182
484062622
51021802
100278165
2716542
323855818
69291
64093
455140
22310982
489033
12666804
32960004
1108250
6235193
366507450
5544535
54254936
21740405
8370
3738236
17471
347386358
338123464
1735828
8391
1633409
224525
1262580
338900101
29624
73125
50789
125592361
423584668
2...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 54ms
memory: 18024kb

input:

100000 100000
2837 9940 6030 9413 2600 1437 9829 4278 660 6655 1571 3167 9455 1012 624 6058 2888 2681 6266 5661 2924 2925 525 3784 6422 4426 3122 3346 9262 9090 9078 9875 4434 6453 4048 7730 3265 3097 3735 1822 7441 6978 2643 142 3811 7179 627 3262 915 2350 2838 2076 5504 7292 2160 4920 6323 3677 55...

output:

252075625
424640180
168263033
365597422
5107537
194173860
47709166
244547988
420622371
480844760
233641056
280175711
176385719
289402283
365597422
387317850
87569060
87695383
158282105
147000391
251735846
13362466
372398145
304918049
108236214
463911665
327070656
457701200
271544874
38385554
4226775...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 57ms
memory: 16480kb

input:

100000 100000
2217 4599 1781 2633 7215 3145 1595 6231 3666 3381 2902 2765 9352 4128 5422 7248 7477 6214 105 5573 6091 7665 2690 8922 8044 6424 2660 5648 2477 6464 5329 6348 3447 531 9448 4947 385 7299 7932 2159 2773 787 3285 4628 4268 4046 1066 6458 2550 5967 1537 6214 431 2177 897 2144 1061 8148 49...

output:

42056727
343471454
86920845
434593089
336848810
410693687
367325841
829
94242481
331724394
185324003
187389586
484335771
331158998
170081437
287076444
301520497
460887728
99663081
398054016
118649464
105824002
198914480
450634027
194114622
312494855
476823119
251856236
445963523
356674221
445273109
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 43ms
memory: 16480kb

input:

100000 100000
3330 2684 9505 1788 7762 1555 7299 1311 9070 5753 1803 1649 9908 1782 4265 4155 9271 5330 2891 4958 3990 9989 6849 4580 3557 7210 3554 1019 3260 5053 2924 8445 3555 1125 3295 3796 5247 5079 6960 9045 7781 6250 4245 2979 3744 3443 6544 6326 5747 4181 2494 5487 9818 9145 8968 2674 6614 4...

output:

455925202
497916458
239437822
284911588
298334363
349404398
306944779
477510599
298000757
284121476
231972359
450255191
473478371
379977393
321203700
158663101
459135896
492551730
340728296
22856
6217557
21969
24534
446693717
444377407
75494372
204148537
113502
199409773
249995310
355095295
26775969...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 69ms
memory: 15904kb

input:

100000 100000
9439 7509 1440 3290 5764 2288 7272 9935 8829 2265 4234 4521 5340 1178 4153 8438 2064 5838 1787 5892 7506 8496 7012 3652 7508 172 4355 5792 5285 5590 9830 4571 5025 8925 6598 3916 1821 3658 9564 2902 4197 2438 7836 7362 6476 8756 5820 5338 5936 3516 5921 2917 3607 5312 7477 7210 3643 47...

output:

178754251
451216332
48090942
176228328
378402089
359304759
483091919
351421777
321238634
166697977
308603123
456061287
274040439
268233428
468801678
4668
230716949
117169866
454934017
318021545
159873935
124761637
324156794
315694268
464157267
244519910
289772629
483518963
153390982
194929075
160572...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 56ms
memory: 15304kb

input:

100000 100000
4498 2035 6447 6899 6082 6418 8922 7792 40 8132 3023 9479 1556 3289 9826 1207 7528 8851 2162 8016 1321 8989 4365 9252 8920 6111 6487 4670 8730 167 6548 2956 5761 3301 6026 9691 9416 9294 9435 4893 202 6500 6545 1922 1534 2074 8935 7856 6912 8981 7955 3123 4621 8692 9590 6437 7674 4574 ...

output:

468520119
76153895
276514251
398392771
269276275
482153656
251318856
384731208
214552745
28830033
259407298
161328799
195818847
230970
123755761
416631
10908
163933096
120397
231534677
36152321
7520162
2252629
281431979
134925
398754890
146841970
65874643
387258424
498923061
80393611
232637285
50452...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 47ms
memory: 15036kb

input:

100000 100000
481 3990 2262 1859 3842 80 6880 9904 5165 7803 1717 7634 8456 7194 1210 7106 8234 9995 4989 261 7076 7070 1759 2045 1430 7733 8977 657 3804 9934 7426 1806 1484 8183 4261 6287 683 8689 4720 4656 3393 2015 7814 2614 5713 1500 2296 3805 1254 5849 2492 5007 1563 3105 8518 38 2193 6567 8251...

output:

449213911
378418899
229376594
400606470
92788861
378840809
391986393
32492136
308343876
108859587
298523480
66061853
341772882
497115838
249513310
350890283
479051053
460910577
419809446
191759170
488065044
208811259
27521060
24444
390956671
456833835
348775717
456646985
96626817
367782999
312402820...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 46ms
memory: 14532kb

input:

100000 100000
7965 435 6833 1508 9725 934 8354 5902 7805 734 9331 3838 5530 2444 4393 8447 697 6201 9185 2204 9494 502 655 1074 9368 7942 2019 9995 6281 774 9130 4266 3528 3837 821 2983 4675 4162 7257 4485 5299 7571 9321 1219 428 9785 3290 7367 6279 3162 4297 3312 58 2059 2568 6279 9293 2393 1235 75...

output:

467127118
273645111
20919
120740
313825778
474103967
303847786
172573339
292128288
382984981
430808735
459967743
186568264
321115170
170832314
469875733
212635975
31896
201044006
479231544
222573293
476284358
462001
194142838
187889696
26312407
211555589
122144437
440912653
353842713
19040
370953257...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 57ms
memory: 14276kb

input:

100000 100000
3705 9790 3829 2272 9072 3912 6047 735 5397 6061 1404 5904 8433 6863 5774 7902 655 3510 162 4091 8552 7651 7621 6178 4578 8060 3915 8371 7356 362 714 7251 5002 30 6959 3640 4726 1068 9383 4995 272 1046 4391 7059 1106 9753 1040 1998 1698 994 9940 9152 6481 5118 9777 1023 9619 535 1462 3...

output:

274178923
749685
327651229
180088
81262
433677171
366723718
184196453
2107
257031559
201413406
141216956
22863155
10469916
535917
54154767
2566
715367
279051
68165318
145889242
3146462
447977
338495421
434050402
494104201
14839
1402682
38845
20487037
1666398
130284
1090852
207808
177760
162490150
58...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 58ms
memory: 14320kb

input:

100000 100000
4713 1929 6029 95 5170 2051 6922 7206 5294 6707 8371 2292 2989 2798 9092 919 1235 104 7415 2683 8207 7386 5311 7220 4223 1224 8928 8332 2600 1635 4985 7194 3461 48 9814 3558 7168 8163 5927 5768 8903 9820 9416 8493 4740 1374 3854 5944 905 1875 140 7592 1854 8227 7811 4196 9050 5204 3142...

output:

117485217
424310292
95640483
484005487
394081824
182852132
260893307
260427115
279695082
42035
398067235
478464042
206055835
109634668
113149
367193511
347012087
66903
254463159
424205363
189956
423744469
93876
697020
236157404
389206652
364610328
343478071
490206304
837
348311304
194467924
48915707...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 51ms
memory: 14348kb

input:

100000 100000
2862 1881 3417 4971 1791 439 6840 2988 8650 1627 721 7430 6186 5686 5155 3129 5828 3812 1531 4396 5430 5980 1949 8864 2663 7794 9077 553 6655 2696 1484 9287 6573 3906 9387 6567 3464 3848 5727 8966 8003 7400 3061 1001 3150 2030 9758 1718 6192 3427 7402 5402 2758 4908 265 8106 2585 2180 ...

output:

101078
493064976
904993
353626473
114301412
76670
140273985
21897
399621
291103211
29064196
2032349
2685073
128489432
488962939
79410
1173835
3138784
1046423
13668265
210353
15262212
171101803
81254591
203725
1860177
489784218
36460785
297205198
9781
26835554
960173
73864699
471609220
19686609
78845...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 58ms
memory: 14304kb

input:

100000 100000
8952 3905 2563 6708 8824 7886 9759 881 3599 5216 3774 572 1973 3159 9887 9130 4638 6341 3423 4554 5913 3693 2524 7563 1981 8407 1388 6858 5550 5087 9350 3262 3118 3745 3746 8672 2633 3084 7153 8239 7681 7989 6456 2437 2588 6895 3054 225 3789 8980 6599 7674 1358 775 5824 2357 9170 5232 ...

output:

57357699
94998701
392710428
441020912
174462619
343937003
98458535
380564060
333738944
192492868
380939327
3368588
1304194
200160594
204684787
254131
202444631
446680043
58150
171955107
302866566
1156308
160655828
42396142
208113
1104677
411298830
427832868
163305336
460820865
218774180
51607495
550...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 48ms
memory: 16748kb

input:

100000 100000
8294 1143 9210 9413 3949 3314 5681 2669 925 4979 9227 1176 2580 8684 4881 6490 5060 4443 8391 1551 1926 8504 137 2571 2905 352 9607 2601 4198 90 5597 7057 4353 2887 2861 3235 7255 2489 7199 4945 5299 7696 3290 8671 5273 9577 9643 4420 3168 9271 9838 2352 8977 3007 1635 2740 3016 7869 5...

output:

175107345
94999826
262989707
211460426
324864848
312254814
492919227
422513071
253161973
377523761
483981771
162353137
169358579
445695381
353488576
360233328
179186826
142514091
113876448
488112124
315298443
232292463
248555344
111786726
150513553
7040884
375524186
321295354
305474727
297955294
184...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 51ms
memory: 16196kb

input:

100000 100000
2736 462 4620 3697 7113 2007 3531 6575 9094 4905 4047 779 8059 8850 8410 8870 5987 7601 3913 3940 8666 3667 4872 2440 6149 6099 838 1113 220 4432 6349 3911 4537 7517 5817 7671 7969 5208 6935 3868 2055 1405 2391 6296 9688 2903 3084 8654 6031 436 1169 5352 7079 1028 7360 5030 8180 8968 2...

output:

477074759
305508386
366088995
226706435
75520033
167489985
121316653
212720408
40777732
403438387
116120348
154864575
459404326
220276935
104532694
45195256
357747043
322765575
44115799
333313042
138855694
488455672
110763818
469568306
454753611
471385365
261262505
196391714
479880072
30715055
45791...

result:

ok 100000 lines

Test #19:

score: 0
Accepted
time: 53ms
memory: 15956kb

input:

100000 100000
2646 2692 979 4069 1353 5804 9757 8851 3766 9683 2380 8478 959 1996 2093 2567 9841 9882 6497 3763 4770 7835 2200 3416 5901 422 1656 1055 3269 431 2013 8363 6177 2593 6837 8025 6036 2340 6379 9062 1725 4528 8683 8125 3689 1701 824 7113 8486 828 1542 3634 9439 5653 1921 204 7903 8535 206...

output:

46765058
278504082
3858657
79012133
14916487
54251220
41207851
32462351
498745879
56116531
48707894
121027903
76777605
206854387
35379481
443404720
23115059
133483073
6925834
99432387
286428268
91452108
98458115
352141443
92094684
97826034
32228949
104704156
15126783
5646578
3787902
77136440
6232676...

result:

ok 100000 lines

Test #20:

score: 0
Accepted
time: 59ms
memory: 15572kb

input:

100000 100000
5092 3914 7801 3962 3273 1408 8691 7878 287 6360 3847 358 3107 2397 112 1094 2613 2705 4800 2985 9335 3412 3460 8596 4348 481 5617 2553 5648 284 6074 9484 5395 4286 2779 9407 6749 4276 2412 9099 9092 1729 2310 8124 4283 5110 2069 5504 6294 3441 3028 1376 8081 3712 4611 2318 6582 4166 6...

output:

308425632
281930664
421890658
52314367
394640692
324551164
8569803
380357591
44862713
186186675
283044388
485547282
414181010
18665219
356066909
105580995
107275969
156718441
110829727
84308858
495104234
480684438
294255662
457907123
393646648
431191656
20517329
29121182
259299589
31680850
91597604
...

result:

ok 100000 lines

Test #21:

score: 0
Accepted
time: 72ms
memory: 15376kb

input:

100000 100000
3855 7345 5685 4096 685 7514 4991 98 3898 5786 5501 8643 9055 3471 2747 137 7108 8697 2909 3702 9648 4358 3548 1951 7493 1831 295 9472 9251 8879 618 5002 3636 4141 6394 4300 8724 594 80 3941 7238 5656 2333 8898 1513 9121 781 1704 2739 369 1130 9441 7866 2525 7533 5796 4730 6966 5988 86...

output:

2090767
6691232
63507273
29832155
478335606
2347523
7430493
940224
4874583
578261
1648141
450420770
3569725
11113813
6293860
2491083
1500248
475927
916374
1145855
9296595
9870533
796917
4669175
266523773
159256018
4297981
7002586
3531165
47388718
5299005
3262967
16145647
7322405
236113272
8662463
70...

result:

ok 100000 lines

Test #22:

score: 0
Accepted
time: 55ms
memory: 15368kb

input:

100000 100000
3444 5744 551 967 5919 1644 3318 8012 459 1619 4101 1872 3759 2337 7254 4375 6396 1293 8242 9865 4108 8241 599 9388 5345 4229 8446 5702 4685 4669 4750 7314 1836 4195 1564 5799 7394 1464 7942 1610 4424 4533 5287 1330 4310 1140 9549 8604 5048 6370 1986 3860 4137 3940 5551 298 9892 5658 8...

output:

50856311
1000246
19866630
1444539
439092138
26661714
442865978
590326
292178869
427072552
215168015
272669997
3155910
303535741
14439129
10289555
7514
464175906
26376
7397985
444050
5669313
82880904
1793281
475725971
6590087
432129208
325002255
36525899
81101662
71113061
3212995
232344331
172211957
...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 56ms
memory: 13800kb

input:

100000 100000
8579 9098 1782 7994 284 1744 1132 8578 6909 1377 6938 194 4084 3680 9687 1827 1518 8448 3468 8814 1502 6423 847 1228 5273 6724 3067 128 3353 2196 9922 6122 921 4266 8879 5064 4098 3755 9325 803 3719 1456 7421 1168 1422 1598 8805 6872 6166 3177 765 2939 2398 7261 3120 3758 6917 9024 678...

output:

489534180
9002723
461272
11517029
3356
739786
466442529
4158137
39023936
182544214
409289842
389017
294443398
3591338
14245983
153302942
225684581
143605
780296
93336106
10623066
3291448
499765848
27132198
55276
478469482
43938
18204292
97412864
33714455
130429510
30512711
32121530
236507674
189418
...

result:

ok 100000 lines

Test #24:

score: 0
Accepted
time: 59ms
memory: 13260kb

input:

100000 100000
6727 4070 2004 7056 2316 982 6809 422 3653 2454 6250 5657 3353 6867 181 5995 1869 6443 5370 9738 5802 6739 7993 3577 8161 3480 2589 9200 6632 6926 5945 1124 3247 2815 5146 2393 9154 5057 8967 9079 2879 961 9991 2812 2471 1986 6616 1201 2726 2840 2254 753 4596 7489 8450 8151 4117 3232 9...

output:

5234
474302
13363
154936833
77333
208865812
150256432
18907178
308424052
2813567
100169
5947638
695485
16595626
50960
79743342
30253
135929489
37388
469580043
10033009
79227640
15611
56140077
1965501
8877607
213313
64268155
57113992
799645
1912883
6878072
99257
6390512
5059604
46124508
411371922
953...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 52ms
memory: 13052kb

input:

100000 100000
5179 6667 9351 2278 1290 437 8982 2483 5077 1303 7 1548 7405 1687 3215 4207 2445 1604 1147 8637 4333 9835 5175 9346 267 6787 6457 8641 3692 6132 673 2976 1512 8895 3586 9092 4812 4316 9061 1884 475 6917 455 8387 4086 4925 3997 1105 9029 4344 6006 2029 501 5282 8844 3889 5989 9716 5159 ...

output:

126212
37889564
961139
3159564
2369680
13612008
452310892
14024759
490336557
9875714
10065501
63766
72553104
9814881
16486
14692605
3438278
78037824
10480789
4289187
121885741
193156801
4237573
266726
455870337
964357
28796
59405386
275096
53304423
372648182
1417388
4412799
10941
178276
2037517
6657...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 57ms
memory: 13188kb

input:

100000 100000
1287 5532 4603 3660 3811 890 1096 98 2862 9716 979 5961 9089 2237 9245 6636 5935 2707 7769 3942 3168 1250 4442 159 5653 8248 5399 466 2308 5827 5747 9352 2424 8007 9989 9072 6433 9754 5531 4552 2014 7339 8639 4003 6760 4551 1678 6721 4222 5185 8189 4541 9110 7051 1031 4576 3784 3482 19...

output:

225809161
558714
498524247
121783442
195030159
121037668
88883164
1305655
4014629
2306044
5863
123888828
36958
6906775
189101
4311201
3540126
219431
170559199
76961610
34630
4728299
3512
14476
299795
5223063
284843847
105518799
2399072
154066
3951
6566041
24285558
4083191
195016565
293086945
1248277...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 54ms
memory: 13676kb

input:

100000 100000
632 6205 3113 2561 4309 5539 1270 3378 8020 5732 9763 1467 4263 8305 2554 4087 5678 8558 2065 8296 6152 7371 5263 3092 6883 4225 4309 6812 8477 4275 9659 1171 3617 1989 2647 8806 4215 6258 1456 4836 8468 4731 4994 7609 2801 5588 5646 2513 9919 7181 9564 7802 973 6017 3629 3332 4864 825...

output:

22087
8412440
7179743
620786
221821
473590457
138940
2075681
479386324
494786569
489101711
75816
3570
42557
114941828
50173
16740020
142706
274419
5566457
117183
942084
12919407
26560886
14501
87756
14542
3247613
442050680
885
45812
14012
436388434
307181
497907994
2782484
45009
3997081
119745
52925...

result:

ok 100000 lines

Test #28:

score: 0
Accepted
time: 51ms
memory: 12740kb

input:

99999 100000
1444 3539 6930 1660 4454 572 5331 8008 5191 1377 4186 5742 5684 5296 2500 3939 450 3089 6663 4446 6375 2264 8441 4399 1073 9675 9837 5038 6654 2493 1433 2840 5093 9670 87 978 1633 9503 6709 7779 7715 6327 2055 6023 7756 882 8236 6198 2906 936 934 6510 6008 2637 2299 6045 1256 1637 433 6...

output:

84843
31596108
255852
288949
2545
38528
11915903
725491
135357624
108657
957324
712095
157210
229630427
116301
100916
90793
4770811
24505981
1149379
81634733
5558071
25477814
6616
196540
73365133
3296794
83205
23294013
20195511
408885382
19156
23935697
490098
1426
9881001
12153
121932
26246449
57556...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 50ms
memory: 12676kb

input:

99932 100000
6813 3036 1267 1167 3452 7872 9178 6099 6965 1123 6953 431 769 2212 2030 5139 3238 7729 5204 9632 6947 9886 44 4196 612 6795 8517 8476 4393 9050 7142 4759 639 9708 6793 6742 8242 7715 732 6040 3314 3080 2335 261 6281 1536 4370 504 6872 3919 7421 355 9483 9285 6436 1376 7743 4302 4339 32...

output:

68724643
7216713
142406304
6660669
358319781
159853
121034
2534513
24213314
37404
51462832
23290
112977
95668
14627991
26497531
394298
78287920
12614
4911833
239008
5980957
32752
42686
43004224
31805109
575235
206949
80420
291240943
13450621
15176
5433271
17996
6383
1530582
8536206
261027
393376
446...

result:

ok 100000 lines

Test #30:

score: 0
Accepted
time: 57ms
memory: 12700kb

input:

99999 100000
7440 9633 8827 4895 5672 3070 5881 6698 7883 7683 9717 3478 4876 437 6929 820 8193 9320 9017 8192 6429 1193 4634 8314 2325 3600 4679 704 9610 9672 5534 8276 1712 7871 813 6842 9326 3325 1315 8782 5974 5751 5784 105 5392 5020 4312 6676 6924 2532 901 8282 1246 6802 7285 3166 1436 7990 759...

output:

56273904
146325991
27636
6127581
500079
1671205
1322
2553409
27207459
329726699
66644185
20655
2373601
234639
2571691
6405552
30155
4025
7129902
196216
25680886
29207
75162811
12503867
273666
4130152
841730
653105
75412
217214560
112068
3154577
193111
3983623
148589996
28333494
32611855
585761
92046...

result:

ok 100000 lines

Test #31:

score: 0
Accepted
time: 55ms
memory: 18168kb

input:

100000 100000
4062 4361 259 808 2158 4583 9966 3261 1204 8591 6923 7230 2444 6693 700 2688 8570 7018 6828 5058 1372 9134 5785 1744 8492 9013 7031 874 6395 2783 4279 98 9046 5562 8307 7912 5472 3915 8266 4067 8715 2687 3208 8344 1830 3567 6771 2869 1294 1769 1002 2758 6243 3180 6166 8265 1910 2526 82...

output:

63598350
432580481
446041993
117531176
146851735
263503610
308149489
381279876
97518859
311648585
451609830
368156573
42004739
196832021
253064795
97503114
118570613
341822808
359478549
323994689
380312219
75595312
437046945
170299289
244577412
171966311
228926188
478808436
286699186
289676221
15772...

result:

ok 100000 lines