CSES - APIO 2016 - Results
Submission details
Task:Boat
Sender:ArktinenKarpalo
Submission time:2019-04-14 02:21:13 +0300
Language:C++
Status:READY
Result:31
Feedback
groupverdictscore
#1ACCEPTED9
#2ACCEPTED22
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4details
#2ACCEPTED0.01 s1, 2, 4details
#3ACCEPTED0.03 s1, 2, 4details
#4ACCEPTED0.02 s1, 2, 4details
#5ACCEPTED0.03 s1, 2, 4details
#6ACCEPTED0.02 s1, 2, 4details
#7ACCEPTED0.02 s1, 2, 4details
#8ACCEPTED0.02 s1, 2, 4details
#9ACCEPTED0.02 s1, 2, 4details
#10ACCEPTED0.02 s1, 2, 4details
#11ACCEPTED0.02 s1, 2, 4details
#12ACCEPTED0.01 s1, 2, 4details
#13ACCEPTED0.01 s1, 2, 4details
#14ACCEPTED0.02 s1, 2, 4details
#15ACCEPTED0.02 s1, 2, 4details
#16ACCEPTED0.01 s1, 2, 4details
#17ACCEPTED0.02 s1, 2, 4details
#18ACCEPTED0.03 s1, 2, 4details
#19ACCEPTED0.02 s1, 2, 4details
#20ACCEPTED0.02 s1, 2, 4details
#21ACCEPTED0.23 s2, 4details
#22ACCEPTED0.23 s2, 4details
#23ACCEPTED0.20 s2, 4details
#24ACCEPTED0.23 s2, 4details
#25ACCEPTED0.23 s2, 4details
#26ACCEPTED0.24 s2, 4details
#27ACCEPTED0.24 s2, 4details
#28ACCEPTED0.24 s2, 4details
#29ACCEPTED0.24 s2, 4details
#30ACCEPTED0.24 s2, 4details
#31ACCEPTED0.90 s2, 4details
#32ACCEPTED0.79 s2, 4details
#33ACCEPTED0.94 s2, 4details
#34ACCEPTED0.81 s2, 4details
#35ACCEPTED0.80 s2, 4details
#36ACCEPTED0.72 s2, 4details
#37ACCEPTED0.88 s2, 4details
#38ACCEPTED0.87 s2, 4details
#39ACCEPTED0.84 s2, 4details
#40ACCEPTED0.72 s2, 4details
#410.33 s3, 4details
#420.31 s3, 4details
#430.31 s3, 4details
#440.32 s3, 4details
#450.31 s3, 4details
#460.34 s3, 4details
#470.31 s3, 4details
#480.31 s3, 4details
#490.30 s3, 4details
#500.31 s3, 4details
#510.34 s3, 4details
#520.31 s3, 4details
#530.32 s3, 4details
#540.31 s3, 4details
#550.32 s3, 4details
#560.32 s3, 4details
#570.32 s3, 4details
#580.31 s3, 4details
#590.31 s3, 4details
#600.33 s3, 4details
#610.31 s4details
#620.32 s4details
#630.32 s4details
#640.31 s4details
#650.31 s4details
#660.33 s4details
#670.32 s4details
#680.31 s4details
#690.33 s4details
#700.31 s4details
#710.32 s4details
#720.32 s4details
#730.31 s4details
#740.30 s4details
#750.30 s4details
#760.33 s4details
#770.33 s4details
#780.32 s4details
#790.33 s4details
#800.32 s4details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:67:6: warning: unused variable 'm' [-Wunused-variable]
   ll m = 0;
      ^

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define M 1000000007
#define N (1<<20)
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

ll ans;
ll sp[N*2], cnt;
ll n, a[555], b[555];
map<int,int> mp;

void add(int k, int x) {
	k += N;
	while(k>=1) {
		sp[k] += x;
		sp[k] %= M;
		k /= 2;
	}
}

ll q(int v, int o) {
	v += N;
	o += N;
	ll ret = 0;
	while(v<=o) {
		if(v%2==1)
			ret += sp[v++];
		if(o%2==0)
			ret += sp[o--];
		ret %= M;
		v /= 2;
		o /= 2;
	}
	return ret;
}

vector<int> ve;

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i] >> b[i];
		for(int j=a[i]; j<=b[i]; j++)
			ve.push_back(j);
	}
	ve.push_back(0);
	sort(ve.begin(), ve.end());
	int ed = -1;
	for(auto u:ve) {
		if(ed != u) {
			cnt++;
			mp[u] = cnt;
			ed = u;
		}
	}
	add(1, 1);
	for(int i=0; i<n; i++) {
		ll m = 0;
		for(int j=b[i]; j>=a[i]; j--) {
			int ind = mp[j];
			ll lk = q(1, ind-1);
			ans += lk;
			ans %= M;
			add(ind, lk);
		}
	}
	cout << ans;
}

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: ACCEPTED

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

correct output
812086153

user output
812086153

Test 17

Group: 1, 2, 4

Verdict: ACCEPTED

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

correct output
908497906

user output
908497906

Test 18

Group: 1, 2, 4

Verdict: ACCEPTED

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

correct output
456073831

user output
456073831

Test 19

Group: 1, 2, 4

Verdict: ACCEPTED

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

correct output
340749954

user output
340749954

Test 20

Group: 1, 2, 4

Verdict: ACCEPTED

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

correct output
957883219

user output
957883219

Test 21

Group: 2, 4

Verdict: ACCEPTED

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

correct output
359985632

user output
359985632

Test 22

Group: 2, 4

Verdict: ACCEPTED

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

correct output
749637311

user output
749637311

Test 23

Group: 2, 4

Verdict: ACCEPTED

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

correct output
459759093

user output
459759093

Test 24

Group: 2, 4

Verdict: ACCEPTED

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

correct output
784900718

user output
784900718

Test 25

Group: 2, 4

Verdict: ACCEPTED

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

correct output
978738112

user output
978738112

Test 26

Group: 2, 4

Verdict: ACCEPTED

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

correct output
807464304

user output
807464304

Test 27

Group: 2, 4

Verdict: ACCEPTED

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

correct output
689161857

user output
689161857

Test 28

Group: 2, 4

Verdict: ACCEPTED

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

correct output
360944141

user output
360944141

Test 29

Group: 2, 4

Verdict: ACCEPTED

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

correct output
436386241

user output
436386241

Test 30

Group: 2, 4

Verdict: ACCEPTED

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

correct output
272725784

user output
272725784

Test 31

Group: 2, 4

Verdict: ACCEPTED

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

correct output
741963819

user output
741963819

Test 32

Group: 2, 4

Verdict: ACCEPTED

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

correct output
550172424

user output
550172424

Test 33

Group: 2, 4

Verdict: ACCEPTED

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

correct output
130181147

user output
130181147

Test 34

Group: 2, 4

Verdict: ACCEPTED

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

correct output
423772182

user output
423772182

Test 35

Group: 2, 4

Verdict: ACCEPTED

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

correct output
954596898

user output
954596898

Test 36

Group: 2, 4

Verdict: ACCEPTED

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

correct output
201460115

user output
201460115

Test 37

Group: 2, 4

Verdict: ACCEPTED

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

correct output
252371564

user output
252371564

Test 38

Group: 2, 4

Verdict: ACCEPTED

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

correct output
68020425

user output
68020425

Test 39

Group: 2, 4

Verdict: ACCEPTED

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

correct output
891271575

user output
891271575

Test 40

Group: 2, 4

Verdict: ACCEPTED

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

correct output
802692144

user output
802692144

Test 41

Group: 3, 4

Verdict:

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

correct output
167281196

user output
(empty)

Test 42

Group: 3, 4

Verdict:

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

correct output
281268921

user output
(empty)

Test 43

Group: 3, 4

Verdict:

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

correct output
720025843

user output
(empty)

Test 44

Group: 3, 4

Verdict:

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

correct output
826742871

user output
(empty)

Test 45

Group: 3, 4

Verdict:

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

correct output
413352225

user output
(empty)

Test 46

Group: 3, 4

Verdict:

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

correct output
44387135

user output
(empty)

Test 47

Group: 3, 4

Verdict:

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

correct output
7399403

user output
(empty)

Test 48

Group: 3, 4

Verdict:

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

correct output
450095995

user output
(empty)

Test 49

Group: 3, 4

Verdict:

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

correct output
888369190

user output
(empty)

Test 50

Group: 3, 4

Verdict:

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

correct output
639276319

user output
(empty)

Test 51

Group: 3, 4

Verdict:

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

correct output
168347538

user output
(empty)

Test 52

Group: 3, 4

Verdict:

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

correct output
837057837

user output
(empty)

Test 53

Group: 3, 4

Verdict:

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

correct output
741328081

user output
(empty)

Test 54

Group: 3, 4

Verdict:

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

correct output
823390527

user output
(empty)

Test 55

Group: 3, 4

Verdict:

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

correct output
362834974

user output
(empty)

Test 56

Group: 3, 4

Verdict:

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

correct output
314359176

user output
(empty)

Test 57

Group: 3, 4

Verdict:

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

correct output
512180893

user output
(empty)

Test 58

Group: 3, 4

Verdict:

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

correct output
396562645

user output
(empty)

Test 59

Group: 3, 4

Verdict:

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

correct output
67963454

user output
(empty)

Test 60

Group: 3, 4

Verdict:

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

correct output
992480862

user output
(empty)

Test 61

Group: 4

Verdict:

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

correct output
186291617

user output
(empty)

Test 62

Group: 4

Verdict:

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

correct output
12136910

user output
(empty)

Test 63

Group: 4

Verdict:

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

correct output
901438370

user output
(empty)

Test 64

Group: 4

Verdict:

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

correct output
599796970

user output
(empty)

Test 65

Group: 4

Verdict:

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

correct output
406223950

user output
(empty)

Test 66

Group: 4

Verdict:

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

correct output
351717365

user output
(empty)

Test 67

Group: 4

Verdict:

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

correct output
165829629

user output
(empty)

Test 68

Group: 4

Verdict:

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

correct output
137319555

user output
(empty)

Test 69

Group: 4

Verdict:

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

correct output
642419612

user output
(empty)

Test 70

Group: 4

Verdict:

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

correct output
760895590

user output
(empty)

Test 71

Group: 4

Verdict:

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

correct output
714815446

user output
(empty)

Test 72

Group: 4

Verdict:

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

correct output
148576527

user output
(empty)

Test 73

Group: 4

Verdict:

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

correct output
673737161

user output
(empty)

Test 74

Group: 4

Verdict:

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

correct output
689919614

user output
(empty)

Test 75

Group: 4

Verdict:

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

correct output
830017844

user output
(empty)

Test 76

Group: 4

Verdict:

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

correct output
698098207

user output
(empty)

Test 77

Group: 4

Verdict:

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

correct output
48652026

user output
(empty)

Test 78

Group: 4

Verdict:

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

correct output
384495356

user output
(empty)

Test 79

Group: 4

Verdict:

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

correct output
77540148

user output
(empty)

Test 80

Group: 4

Verdict:

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

correct output
353197380

user output
(empty)