CSES - APIO 2016 - Results
Submission details
Task:Boat
Sender:henrikaalto
Submission time:2019-04-14 18:18:31 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 4details
#2ACCEPTED0.02 s1, 2, 4details
#3ACCEPTED0.01 s1, 2, 4details
#4ACCEPTED0.02 s1, 2, 4details
#5ACCEPTED0.02 s1, 2, 4details
#6ACCEPTED0.04 s1, 2, 4details
#7ACCEPTED0.03 s1, 2, 4details
#8ACCEPTED0.02 s1, 2, 4details
#9ACCEPTED0.03 s1, 2, 4details
#10ACCEPTED0.01 s1, 2, 4details
#11ACCEPTED0.02 s1, 2, 4details
#12ACCEPTED0.01 s1, 2, 4details
#13ACCEPTED0.03 s1, 2, 4details
#14ACCEPTED0.01 s1, 2, 4details
#15ACCEPTED0.01 s1, 2, 4details
#160.02 s1, 2, 4details
#170.02 s1, 2, 4details
#180.02 s1, 2, 4details
#190.02 s1, 2, 4details
#200.02 s1, 2, 4details
#210.02 s2, 4details
#220.01 s2, 4details
#230.02 s2, 4details
#240.02 s2, 4details
#250.02 s2, 4details
#260.02 s2, 4details
#270.04 s2, 4details
#280.01 s2, 4details
#290.03 s2, 4details
#300.02 s2, 4details
#310.02 s2, 4details
#320.02 s2, 4details
#330.02 s2, 4details
#340.03 s2, 4details
#350.02 s2, 4details
#360.02 s2, 4details
#370.01 s2, 4details
#380.01 s2, 4details
#390.02 s2, 4details
#400.03 s2, 4details
#410.02 s3, 4details
#420.02 s3, 4details
#430.02 s3, 4details
#440.01 s3, 4details
#450.02 s3, 4details
#460.02 s3, 4details
#470.02 s3, 4details
#480.02 s3, 4details
#490.03 s3, 4details
#500.02 s3, 4details
#510.02 s3, 4details
#520.02 s3, 4details
#530.01 s3, 4details
#540.01 s3, 4details
#550.03 s3, 4details
#560.02 s3, 4details
#570.01 s3, 4details
#580.02 s3, 4details
#590.03 s3, 4details
#600.02 s3, 4details
#610.02 s4details
#620.02 s4details
#630.03 s4details
#640.02 s4details
#650.02 s4details
#660.01 s4details
#670.03 s4details
#680.01 s4details
#690.02 s4details
#700.02 s4details
#710.04 s4details
#720.03 s4details
#730.03 s4details
#740.03 s4details
#750.02 s4details
#760.01 s4details
#770.02 s4details
#780.03 s4details
#790.01 s4details
#800.02 s4details

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n; cin >> n;
  int d[n+1];
  map<int,int> m;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x >> x;
    m[x] = 1;
    d[i] = x;
  }
  int c = 0;
  for (auto &u : m) {
    u.second = ++c;
  }
  for (int i = 1; i <= n; ++i) {
    d[i] = m[d[i]];
  }
  int dp[555] = {};
  int mod = 1e9 + 7;
  int mx = 554;
  dp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    long s = 0;
    for (int j = 0; j < 555; ++j) {
      s += dp[j];
      s %= mod;
    }
    long sz = 0;
    for (int j = 0; j <= d[i]-1; ++j) {
      sz += dp[j];
      sz %= mod;
    }
    dp[d[i]] += sz;
//    dp[0] = s;
/*
    printf("\n");
    printf("\n");
    for (int j =0 ; j < 10; ++j) {
      printf("%d ",dp[j]);
    }
    printf("\n");
    printf("\n");
*/
  }
  long ans = 0;
  for (int j = 0; j <= mx; ++j) {
    ans += dp[j];
    ans %= mod;
  }
  printf("%ld\n",(ans-1+mod) % mod);
}

Test details

Test 1

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
308810287 308810287
53564892 53564892
316377768 316377768
420249597 420249597
...

correct output
553232367

user output
553232367

Test 2

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
259419237 259419237
71604627 71604627
140848485 140848485
45258355 45258355
...

correct output
818775560

user output
818775560

Test 3

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
409222683 409222683
424488829 424488829
415529128 415529128
852855991 852855991
...

correct output
676116158

user output
676116158

Test 4

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
619714633 619714633
470637076 470637076
88903555 88903555
219610285 219610285
...

correct output
826747956

user output
826747956

Test 5

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
781499655 781499655
32818153 32818153
128804256 128804256
106725036 106725036
...

correct output
796144690

user output
796144690

Test 6

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
471686 471686
89197062 89197062
4486841 4486841
223318132 223318132
...

correct output
287072213

user output
287072213

Test 7

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
753345 753345
807697 807697
1544540 1544540
2467957 2467957
...

correct output
454779099

user output
454779099

Test 8

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
2121408 2121408
2590977 2590977
2954510 2954510
3391039 3391039
...

correct output
794869016

user output
794869016

Test 9

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
1067490 1067490
187728209 187728209
2331190 2331190
2402125 2402125
...

correct output
620087548

user output
620087548

Test 10

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
2212852 2212852
2573958 2573958
3807064 3807064
4541303 4541303
...

correct output
271082404

user output
271082404

Test 11

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
524893 524893
2750062 2750062
3570891 3570891
4638547 4638547
...

correct output
822157788

user output
822157788

Test 12

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
1540808 1540808
1937564 1937564
5283319 5283319
7804041 7804041
...

correct output
455632768

user output
455632768

Test 13

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
245210 245210
386280 386280
901085 901085
1260725 1260725
...

correct output
902897517

user output
902897517

Test 14

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
1114055 1114055
1562475 1562475
2053281 2053281
3495973 3495973
...

correct output
405249073

user output
405249073

Test 15

Group: 1, 2, 4

Verdict: ACCEPTED

input
500
1221260 1221260
1536448 1536448
1596219 1596219
3817144 3817144
...

correct output
346378962

user output
346378962

Test 16

Group: 1, 2, 4

Verdict:

input
500
158450518 158450518
398419544 398419544
15852367 15852367
147721606 147721606
...

correct output
812086153

user output
417240088

Test 17

Group: 1, 2, 4

Verdict:

input
500
557602055 557602055
181162629 181162629
632543712 632543712
666184058 666184058
...

correct output
908497906

user output
27469991

Test 18

Group: 1, 2, 4

Verdict:

input
500
98524121 98524121
114027386 114027386
126071599 126071599
190426100 190426100
...

correct output
456073831

user output
680733179

Test 19

Group: 1, 2, 4

Verdict:

input
500
242086234 242086234
698376795 698376795
261877241 261877241
844564041 844564041
...

correct output
340749954

user output
818044310

Test 20

Group: 1, 2, 4

Verdict:

input
500
96243961 96243961
558940945 558940945
262224079 262224079
535961870 535961870
...

correct output
957883219

user output
351398351

Test 21

Group: 2, 4

Verdict:

input
500
2425 2847
684 2839
462 1824
1522 4144
...

correct output
359985632

user output
595391332

Test 22

Group: 2, 4

Verdict:

input
500
339 3243
558 2133
2178 4549
807 2946
...

correct output
749637311

user output
465839491

Test 23

Group: 2, 4

Verdict:

input
500
557 992
63 1129
802 5128
2764 5038
...

correct output
459759093

user output
366353881

Test 24

Group: 2, 4

Verdict:

input
500
1602 1738
3878 4429
1499 1686
426 4555
...

correct output
784900718

user output
596954180

Test 25

Group: 2, 4

Verdict:

input
500
817 4516
381 2523
903 5196
3618 4260
...

correct output
978738112

user output
106879487

Test 26

Group: 2, 4

Verdict:

input
500
1 1925
2 1925
4 1931
8 1932
...

correct output
807464304

user output
525120594

Test 27

Group: 2, 4

Verdict:

input
500
26 2087
39 2091
42 2093
501 2515
...

correct output
689161857

user output
258395853

Test 28

Group: 2, 4

Verdict:

input
500
4 1905
7 1916
15 1916
18 1920
...

correct output
360944141

user output
455796256

Test 29

Group: 2, 4

Verdict:

input
500
12 2018
1754 3604
17 2023
19 2026
...

correct output
436386241

user output
606465129

Test 30

Group: 2, 4

Verdict:

input
500
1 1975
10 1979
19 1980
33 1988
...

correct output
272725784

user output
993579294

Test 31

Group: 2, 4

Verdict:

input
500
257392824 257393039
257206183 257207501
257207498 257209286
257209284 257210501
...

correct output
741963819

user output
984598307

Test 32

Group: 2, 4

Verdict:

input
500
359763520 359764666
359764664 359765010
359765010 359765531
359765530 359766113
...

correct output
550172424

user output
640061702

Test 33

Group: 2, 4

Verdict:

input
500
275094475 275095639
275095639 275095814
275095811 275097717
275097710 275098688
...

correct output
130181147

user output
85728773

Test 34

Group: 2, 4

Verdict:

input
500
339490516 339491326
339491322 339493093
339493090 339495078
339495075 339495504
...

correct output
423772182

user output
284092873

Test 35

Group: 2, 4

Verdict:

input
500
455881331 455881991
455881983 455883495
455883495 455884407
455884400 455885135
...

correct output
954596898

user output
569509486

Test 36

Group: 2, 4

Verdict:

input
500
23132758 23136784
22787999 22792740
22316316 22316986
22585370 22588120
...

correct output
201460115

user output
605680425

Test 37

Group: 2, 4

Verdict:

input
500
22302917 22303387
22837337 22841765
22597675 22597827
22577081 22577708
...

correct output
252371564

user output
933063060

Test 38

Group: 2, 4

Verdict:

input
500
22526726 22528592
22482585 22484632
22551295 22552329
22318130 22319190
...

correct output
68020425

user output
782442566

Test 39

Group: 2, 4

Verdict:

input
500
22391177 22393392
22474300 22476662
22550513 22553373
22674877 22678495
...

correct output
891271575

user output
216801755

Test 40

Group: 2, 4

Verdict:

input
500
22932573 22933372
23025447 23034719
22231801 22232122
22615796 22616882
...

correct output
802692144

user output
942440367

Test 41

Group: 3, 4

Verdict:

input
100
191358459 947004691
342443850 366915813
22574423 36448174
228846908 747282766
...

correct output
167281196

user output
25747321

Test 42

Group: 3, 4

Verdict:

input
100
383581393 816569935
148622782 696834692
514001933 750928139
133856778 549893268
...

correct output
281268921

user output
4723157

Test 43

Group: 3, 4

Verdict:

input
100
47376766 664313233
394991487 987813102
567510996 864092804
474261027 978587193
...

correct output
720025843

user output
10551263

Test 44

Group: 3, 4

Verdict:

input
100
298419616 843564930
59305155 297269005
531834796 928938169
441735148 973559139
...

correct output
826742871

user output
11431378

Test 45

Group: 3, 4

Verdict:

input
100
555348798 709755670
168305976 212781628
228849382 744856727
56990747 168240982
...

correct output
413352225

user output
17100957

Test 46

Group: 3, 4

Verdict:

input
100
4286365 334929271
4981537 338808196
23557681 356699543
33398390 358101339
...

correct output
44387135

user output
291544963

Test 47

Group: 3, 4

Verdict:

input
100
20024968 371243560
330351675 712369644
23278781 380556271
318072353 701674210
...

correct output
7399403

user output
783500563

Test 48

Group: 3, 4

Verdict:

input
100
9198943 369659170
252989538 575101349
19510121 374889661
21431381 384205475
...

correct output
450095995

user output
952500105

Test 49

Group: 3, 4

Verdict:

input
100
1706537 371893895
4810220 372381936
340358769 711984953
297035471 662141002
...

correct output
888369190

user output
772852944

Test 50

Group: 3, 4

Verdict:

input
100
48265690 374587600
10490181 339498659
10924429 341652033
11618636 342565709
...

correct output
639276319

user output
881096456

Test 51

Group: 3, 4

Verdict:

input
100
1742949 162238200
5430997 752445937
5803156 568237652
11057966 45859889
...

correct output
168347538

user output
144077684

Test 52

Group: 3, 4

Verdict:

input
100
1648626 403768768
5159779 392060583
6900671 187788672
13032456 837080381
...

correct output
837057837

user output
956354598

Test 53

Group: 3, 4

Verdict:

input
100
53206780 701552611
13840621 218491257
330624565 998078904
98973769 911024153
...

correct output
741328081

user output
343196644

Test 54

Group: 3, 4

Verdict:

input
100
19180936 742907446
30712602 726016511
115465166 974039212
38459157 639067171
...

correct output
823390527

user output
181931177

Test 55

Group: 3, 4

Verdict:

input
100
1886273 642680910
6943573 931446211
14880352 64904283
103201125 477902958
...

correct output
362834974

user output
659654201

Test 56

Group: 3, 4

Verdict:

input
100
77671609 272592863
77671609 716914494
27023382 928910161
677153236 902303504
...

correct output
314359176

user output
7250281

Test 57

Group: 3, 4

Verdict:

input
100
192581477 989087814
299989070 611050414
92082640 929372492
119829869 323037264
...

correct output
512180893

user output
4444278

Test 58

Group: 3, 4

Verdict:

input
100
41487637 487367211
275195437 421488090
710727204 796623144
188296381 205905055
...

correct output
396562645

user output
85139779

Test 59

Group: 3, 4

Verdict:

input
100
78320887 403473171
572032610 981242610
11978066 791716543
114129022 595561934
...

correct output
67963454

user output
1836364

Test 60

Group: 3, 4

Verdict:

input
100
259780149 408143598
295251037 615898303
540680082 605229613
105297737 408143598
...

correct output
992480862

user output
3554475

Test 61

Group: 4

Verdict:

input
500
851440668 951159939
387881127 613157870
93998278 492274255
664765993 836716756
...

correct output
186291617

user output
84305892

Test 62

Group: 4

Verdict:

input
500
218084335 642361724
126684080 363862754
581542344 589281034
410530895 670487908
...

correct output
12136910

user output
516445509

Test 63

Group: 4

Verdict:

input
500
173292182 726063470
617485005 979754208
327945446 845344742
95065426 408831073
...

correct output
901438370

user output
557400911

Test 64

Group: 4

Verdict:

input
500
96959114 721679272
388873527 518209465
244499478 892522869
536026274 775212871
...

correct output
599796970

user output
482363879

Test 65

Group: 4

Verdict:

input
500
624931439 724401192
432867185 616812682
16470026 111027857
690598502 924072970
...

correct output
406223950

user output
38331661

Test 66

Group: 4

Verdict:

input
500
70275 371693882
570790 371990164
3035796 372540461
4414053 373776666
...

correct output
351717365

user output
233689896

Test 67

Group: 4

Verdict:

input
500
729736 370767975
2231620 371149053
2288939 372469401
3404776 379076522
...

correct output
165829629

user output
646575796

Test 68

Group: 4

Verdict:

input
500
352905 379085200
600400 381084154
861491 381344549
1383462 381588470
...

correct output
137319555

user output
654520743

Test 69

Group: 4

Verdict:

input
500
1675225 369557170
2836091 369750325
2869701 369838188
3380918 371071293
...

correct output
642419612

user output
929024704

Test 70

Group: 4

Verdict:

input
500
245630 387992612
1806972 388203745
3634120 392194935
4649171 392745566
...

correct output
760895590

user output
906654730

Test 71

Group: 4

Verdict:

input
500
529 992540448
618931 206150834
1061954 66232804
5839872 517219526
...

correct output
714815446

user output
902560741

Test 72

Group: 4

Verdict:

input
500
1012923 941184633
2343835 300578559
4351415 620228740
5191655 951674812
...

correct output
148576527

user output
801780018

Test 73

Group: 4

Verdict:

input
500
83005 398503494
260204 895810192
1474179 274129536
1907933 660406719
...

correct output
673737161

user output
533927150

Test 74

Group: 4

Verdict:

input
500
1003351 765901035
2673296 856874893
2886060 705226595
3790986 708617430
...

correct output
689919614

user output
528195936

Test 75

Group: 4

Verdict:

input
500
642542 934933733
3354746 184437812
6094168 670136353
6470039 615718936
...

correct output
830017844

user output
273397851

Test 76

Group: 4

Verdict:

input
500
205808516 451346097
470412594 696069181
420735847 812683185
352804737 555342470
...

correct output
698098207

user output
331841915

Test 77

Group: 4

Verdict:

input
500
61836209 686625091
258482931 852176106
577825245 668325225
176164759 220687770
...

correct output
48652026

user output
738342145

Test 78

Group: 4

Verdict:

input
500
457667772 855811880
232784559 507073783
4912688 950398058
588850701 675524294
...

correct output
384495356

user output
835461454

Test 79

Group: 4

Verdict:

input
500
751651659 915544886
55536655 676174191
436342385 773549902
436342385 810391996
...

correct output
77540148

user output
970675813

Test 80

Group: 4

Verdict:

input
500
273778462 924066200
314166350 929804773
346154110 818228013
116351414 312473009
...

correct output
353197380

user output
557726221