QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142650#2. Boatxiaowuc6100 ✓183ms3800kbC++144.3kb2023-08-19 16:31:032023-08-19 16:31:05

Judging History

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

  • [2023-08-19 16:31:05]
  • 评测
  • 测评结果:100
  • 用时:183ms
  • 内存:3800kb
  • [2023-08-19 16:31:03]
  • 提交

answer

#include<stdio.h>
#include<cmath>
#include<complex>
#include<algorithm>
#include<vector>
#define mod 1000000007
using namespace std;
 
typedef long long lld;
typedef complex<double> base;
 
struct qry {
    int ix;
    lld x, pm;
    bool operator< (const qry& c) const {
        return x<c.x;
    }
}que[11010];
 
int n, chk[5050], act, qcn;
lld dy[5050], inv[5050];
 
void fft(vector <base> &a, bool invert){
    int n = a.size();
    for(int i=1,j=0; i<n; i++){
        int bit = n>>1;
        for(; j>=bit; bit>>=1)j -= bit;
        j += bit;
        if(i<j)swap(a[i], a[j]);
    }
    for(int len=2; len<=n; len<<=1){
        double ang = 2*M_PI/len*(invert?-1:1);
        base wlen(cos(ang), sin(ang));
        for(int i=0; i<n; i+=len){
            base w(1);
            for(int j=0; j<len/2; j++){
                base u=a[i+j], v=a[i+j+len/2]*w;
                a[i+j] = u+v;
                a[i+j+len/2] = u-v;
                w *= wlen;
            }
        }
    }
    if(invert){
        for(int i=0; i<n; i++)a[i] /= n;
    }
}
 
void convolution(vector<lld>& x, vector<lld>& y, const int sz){
    vector<base> fa1, fa2, fb1, fb2;
    int n, i;
    for(n=1; n<sz; n<<=1);
    for(i=0; i<n; i++){
        fa1.push_back(0), fa2.push_back(0);
        fb1.push_back(0), fb2.push_back(0);
    }
    for(i=0; i<sz; i++){
        fa1.push_back(x[i]/30000), fa2.push_back(x[i]%30000);
        fb1.push_back(y[i]/30000), fb2.push_back(y[i]%30000);
    }
    n<<=1;
    fa1.resize(n), fa2.resize(n);
    fb1.resize(n), fb2.resize(n);
    fft(fa1, 0), fft(fa2, 0);
    fft(fb1, 0), fft(fb2, 0);
    for(i=0; i<n; i++){
        base a1b1 = fa1[i]*fb1[i], a1b2 = fa1[i]*fb2[i];
        base a2b1 = fa2[i]*fb1[i], a2b2 = fa2[i]*fb2[i];
        fa1[i] = a1b1, fa2[i] = a1b2, fb1[i] = a2b1, fb2[i] = a2b2;
    }
    fft(fa1, 1), fft(fa2, 1);
    fft(fb1, 1), fft(fb2, 1);
    for(i=0; i<sz; i++){
        lld a1b1, a1b2, a2b1, a2b2;
        a1b1 = lld(fa1[i].real() + (fa1[i].real()>0 ? 0.5:-0.5)), a1b1%=mod;
        a1b2 = lld(fa2[i].real() + (fa2[i].real()>0 ? 0.5:-0.5)), a1b2%=mod;
        a2b1 = lld(fb1[i].real() + (fb1[i].real()>0 ? 0.5:-0.5)), a2b1%=mod;
        a2b2 = lld(fb2[i].real() + (fb2[i].real()>0 ? 0.5:-0.5)), a2b2%=mod;
        x[i] = (a1b1*900000000ll + (a1b2+a2b1)*30000ll + a2b2)%mod;
    }
}
 
/*
void convolution(vector<lld>& x, vector<lld>& y, const int sz){
    int i, j;
    for(i=sz-1; i>=0; i--){
        lld sum=0;
        for(j=0; j<=i; j++){
            sum+=x[j]*y[i-j];
            sum%=mod;
        }
        x[i]=sum;
    }
}*/
 
lld pw(lld a, lld b){
    if(b<=0)return 1;
    lld g=pw(a,b/2);
    g=(g*g)%mod;
    if(b%2)g=(g*a)%mod;
    return g;
}
 
int main(){
    int i;
    lld pv;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        lld s, e;
        scanf("%lld%lld", &s, &e);
        que[qcn].ix=i, que[qcn].x=s, que[qcn++].pm=1;
        que[qcn].ix=i, que[qcn].x=e+1, que[qcn++].pm=-1;
    }
    for(i=1; i<=n; i++)inv[i]=pw(i, mod-2);
    sort(que, que+qcn);
     
    pv=0;
    for(i=0; i<qcn; i++){
        if(pv<que[i].x && act){
            lld psum=-1, sum=0, mul=1;
            int j, ccn=0;
            vector <lld> p, q;
            for(j=0; j<n; j++){
                if(chk[j]){
                    lld arg = sum-psum+mod;
                    while(arg>=mod)arg-=mod;
                    mul *= (que[i].x-pv+ccn)*inv[ccn+1]%mod;
                    mul %= mod;
                    p.push_back(arg);
                    q.push_back(mul);
                    psum=sum;
                    ccn++;
                }
                sum += dy[j];
                if(sum >= mod)sum -= mod;
            }
            convolution(p, q, ccn);
            for(j=ccn=0; j<n; j++){
                if(chk[j]){
                    dy[j] += p[ccn];
                    if(dy[j] >= mod)dy[j] -= mod;
                    ccn++;
                }
            }
        }
/*      printf("%lld ~ %lld:\n", pv, que[i].x-1);
        for(int j=0; j<n; j++)printf("%lld ", dy[j]);
        puts("");*/
        pv = que[i].x;
        chk[que[i].ix] += que[i].pm, act += que[i].pm;
    }
     
    lld sum=0;
    for(i=0; i<n; i++){
        sum += dy[i];
        if(sum >= mod)sum -= mod;
    }
    printf("%lld", sum);
    return 0;
}

詳細信息

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 0ms
memory: 3100kb

input:

500
308810287 308810287
53564892 53564892
316377768 316377768
420249597 420249597
731165653 731165653
319087025 319087025
153776963 153776963
425464316 425464316
651047701 651047701
142502072 142502072
31632388 31632388
572337890 572337890
400220429 400220429
414382974 414382974
279400752 279400752
...

output:

553232367

result:

ok single line: '553232367'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3156kb

input:

500
259419237 259419237
71604627 71604627
140848485 140848485
45258355 45258355
417882612 417882612
70908445 70908445
647789306 647789306
269825295 269825295
528839543 528839543
35956097 35956097
555387597 555387597
114446845 114446845
663753828 663753828
236039707 236039707
730686123 730686123
1874...

output:

818775560

result:

ok single line: '818775560'

Test #3:

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

input:

500
409222683 409222683
424488829 424488829
415529128 415529128
852855991 852855991
199702963 199702963
121993369 121993369
660424994 660424994
247915283 247915283
11387254 11387254
198385312 198385312
49663799 49663799
640850062 640850062
123783577 123783577
460294327 460294327
41816505 41816505
77...

output:

676116158

result:

ok single line: '676116158'

Test #4:

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

input:

500
619714633 619714633
470637076 470637076
88903555 88903555
219610285 219610285
213164397 213164397
438259138 438259138
640791314 640791314
306721667 306721667
225421135 225421135
233222391 233222391
205820722 205820722
692168797 692168797
48417870 48417870
398991106 398991106
393107546 393107546
...

output:

826747956

result:

ok single line: '826747956'

Test #5:

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

input:

500
781499655 781499655
32818153 32818153
128804256 128804256
106725036 106725036
373502067 373502067
522124816 522124816
327019589 327019589
28487843 28487843
242370575 242370575
340419621 340419621
156024191 156024191
293959833 293959833
651063779 651063779
185398156 185398156
23810548 23810548
15...

output:

796144690

result:

ok single line: '796144690'

Test #6:

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

input:

500
471686 471686
89197062 89197062
4486841 4486841
223318132 223318132
5382727 5382727
6119192 6119192
6920252 6920252
7400635 7400635
8953527 8953527
9453109 9453109
10297661 10297661
11088577 11088577
11747318 11747318
13120793 13120793
13620658 13620658
13858796 13858796
14388301 14388301
146049...

output:

287072213

result:

ok single line: '287072213'

Test #7:

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

input:

500
753345 753345
807697 807697
1544540 1544540
2467957 2467957
2620013 2620013
4381651 4381651
5343267 5343267
5650005 5650005
6291995 6291995
7239714 7239714
8727983 8727983
9137734 9137734
9167898 9167898
10039210 10039210
10042325 10042325
11550040 11550040
11642995 11642995
12967910 12967910
13...

output:

454779099

result:

ok single line: '454779099'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3212kb

input:

500
2121408 2121408
2590977 2590977
2954510 2954510
3391039 3391039
3456654 3456654
3749072 3749072
4891660 4891660
5175214 5175214
25595893 25595893
8207147 8207147
8471111 8471111
8542387 8542387
8571053 8571053
9561645 9561645
9686851 9686851
9766228 9766228
10735337 10735337
11488198 11488198
11...

output:

794869016

result:

ok single line: '794869016'

Test #9:

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

input:

500
1067490 1067490
187728209 187728209
2331190 2331190
2402125 2402125
2635735 2635735
2952562 2952562
2996248 2996248
3434435 3434435
3506579 3506579
4727619 4727619
4948298 4948298
6100013 6100013
7237778 7237778
9714151 9714151
11703576 11703576
148126723 148126723
14940558 14940558
16312000 163...

output:

620087548

result:

ok single line: '620087548'

Test #10:

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

input:

500
2212852 2212852
2573958 2573958
3807064 3807064
4541303 4541303
4738320 4738320
5370702 5370702
5432558 5432558
371112074 371112074
8844474 8844474
8853776 8853776
9304445 9304445
11586488 11586488
12141143 12141143
12744747 12744747
15599671 15599671
15817906 15817906
146704510 146704510
163676...

output:

271082404

result:

ok single line: '271082404'

Test #11:

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

input:

500
524893 524893
2750062 2750062
3570891 3570891
4638547 4638547
4674487 4674487
4862482 4862482
5519675 5519675
9272918 9272918
9748535 9748535
9864262 9864262
10265009 10265009
15407366 15407366
16115070 16115070
16840848 16840848
17360063 17360063
17484830 17484830
17877302 17877302
19863611 198...

output:

822157788

result:

ok single line: '822157788'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3212kb

input:

500
1540808 1540808
1937564 1937564
5283319 5283319
7804041 7804041
8433829 8433829
823139355 823139355
10494027 10494027
10546482 10546482
10621868 10621868
12153702 12153702
14415814 14415814
14426450 14426450
14804293 14804293
397985392 397985392
16988704 16988704
18836771 18836771
19696492 19696...

output:

455632768

result:

ok single line: '455632768'

Test #13:

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

input:

500
245210 245210
386280 386280
901085 901085
1260725 1260725
2429888 2429888
2654946 2654946
5006386 5006386
5371303 5371303
5813686 5813686
6154770 6154770
6350055 6350055
6508782 6508782
7456974 7456974
8140422 8140422
10003117 10003117
10268361 10268361
10642582 10642582
12660838 12660838
129157...

output:

902897517

result:

ok single line: '902897517'

Test #14:

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

input:

500
1114055 1114055
1562475 1562475
2053281 2053281
3495973 3495973
5137725 5137725
5658217 5658217
8216527 8216527
309196291 309196291
10687446 10687446
12153021 12153021
13249709 13249709
14657222 14657222
16140910 16140910
16171193 16171193
17460544 17460544
53076303 53076303
18954216 18954216
20...

output:

405249073

result:

ok single line: '405249073'

Test #15:

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

input:

500
1221260 1221260
1536448 1536448
1596219 1596219
3817144 3817144
5547038 5547038
5835095 5835095
8575834 8575834
13879314 13879314
13995687 13995687
14266986 14266986
16029893 16029893
16046286 16046286
16527064 16527064
35000863 35000863
18449319 18449319
18985127 18985127
19461392 19461392
1948...

output:

346378962

result:

ok single line: '346378962'

Test #16:

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

input:

500
158450518 158450518
398419544 398419544
15852367 15852367
147721606 147721606
189509271 189509271
12933510 12933510
38041970 38041970
268576530 268576530
752348312 752348312
158603479 158603479
515657574 515657574
277993122 277993122
158450518 158450518
8997617 8997617
841673344 841673344
117222...

output:

812086153

result:

ok single line: '812086153'

Test #17:

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

input:

500
557602055 557602055
181162629 181162629
632543712 632543712
666184058 666184058
682380195 682380195
553262662 553262662
632543712 632543712
635814815 635814815
229155517 229155517
208595757 208595757
472562424 472562424
714082069 714082069
728505635 728505635
321600780 321600780
109570005 109570...

output:

908497906

result:

ok single line: '908497906'

Test #18:

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

input:

500
98524121 98524121
114027386 114027386
126071599 126071599
190426100 190426100
3643106 3643106
98524121 98524121
818260656 818260656
177510656 177510656
149595703 149595703
114980573 114980573
163331808 163331808
98524121 98524121
114980573 114980573
659960023 659960023
7634737 7634737
662508335 ...

output:

456073831

result:

ok single line: '456073831'

Test #19:

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

input:

500
242086234 242086234
698376795 698376795
261877241 261877241
844564041 844564041
183035910 183035910
382328127 382328127
80253578 80253578
203346776 203346776
912382968 912382968
93064185 93064185
431774176 431774176
278790959 278790959
363084713 363084713
273437132 273437132
678641564 678641564
...

output:

340749954

result:

ok single line: '340749954'

Test #20:

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

input:

500
96243961 96243961
558940945 558940945
262224079 262224079
535961870 535961870
518474366 518474366
96243961 96243961
783348140 783348140
181632008 181632008
584798581 584798581
173499219 173499219
52148740 52148740
2733695 2733695
2733695 2733695
284315759 284315759
643050814 643050814
457614794 ...

output:

957883219

result:

ok single line: '957883219'

Subtask #2:

score: 22
Accepted

Dependency #1:

100%
Accepted

Test #21:

score: 22
Accepted
time: 62ms
memory: 3796kb

input:

500
2425 2847
684 2839
462 1824
1522 4144
2140 3238
1750 4806
224 703
3351 5040
2882 2950
345 3747
794 2651
991 1127
639 2031
1118 2638
1264 2846
1537 2048
745 1969
4864 4903
3354 3752
1291 4991
448 4482
297 1945
4822 4929
2538 5080
1883 4299
828 4709
1273 4804
1927 4361
254 1956
832 1451
2791 2902
...

output:

359985632

result:

ok single line: '359985632'

Test #22:

score: 0
Accepted
time: 65ms
memory: 3596kb

input:

500
339 3243
558 2133
2178 4549
807 2946
1183 1973
1338 2665
87 245
1836 3299
1541 4561
2167 5058
224 4908
1163 3638
1130 1657
882 2183
1261 4670
2180 4996
606 4329
268 1036
1623 2730
1680 2268
595 1838
304 4629
911 4274
1060 2803
3012 3714
2638 3860
1108 5077
4506 4843
2137 2370
2832 3573
1367 3217...

output:

749637311

result:

ok single line: '749637311'

Test #23:

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

input:

500
557 992
63 1129
802 5128
2764 5038
2467 2764
1923 4649
2864 3884
1601 5129
2936 4853
1412 3047
516 3107
1682 4510
3701 5039
964 4515
3562 4021
1446 2485
1026 1272
1605 4635
1154 3508
681 891
1659 2750
146 1782
858 2603
191 3115
373 1560
1495 3780
1908 5096
4664 5022
1374 1734
1596 4385
1425 4634...

output:

459759093

result:

ok single line: '459759093'

Test #24:

score: 0
Accepted
time: 116ms
memory: 3800kb

input:

500
1602 1738
3878 4429
1499 1686
426 4555
778 4804
99 1775
2139 4940
2260 5097
4388 4831
1188 3176
1769 3759
359 1658
855 4259
1763 4643
4541 4918
2610 4122
363 5173
972 2325
952 1600
1645 1991
2956 3749
2939 3497
2638 4944
472 2419
2968 4437
2829 2957
4320 4700
1119 2147
3701 4255
4662 5159
454 19...

output:

784900718

result:

ok single line: '784900718'

Test #25:

score: 0
Accepted
time: 60ms
memory: 3656kb

input:

500
817 4516
381 2523
903 5196
3618 4260
592 4313
313 1075
3688 4289
4511 4657
2000 2061
1093 4711
700 3366
1277 5086
1977 5048
146 3724
3760 4247
17 2945
757 3791
3704 4676
77 2747
1025 3585
863 4966
1590 2840
1330 2064
541 1238
265 1135
1908 4892
1138 3203
2812 4292
1146 2793
794 3829
592 2814
156...

output:

978738112

result:

ok single line: '978738112'

Test #26:

score: 0
Accepted
time: 91ms
memory: 3468kb

input:

500
1 1925
2 1925
4 1931
8 1932
12 1933
19 1934
21 1936
26 1938
28 1945
36 1950
39 1951
44 1960
47 1968
50 1968
52 1970
62 1977
69 1981
85 1990
101 1991
105 1992
110 2002
112 2002
113 2003
117 2004
130 2011
134 2016
134 2019
135 2026
137 2057
142 2065
145 2071
157 2073
165 2078
165 2078
1796 3816
17...

output:

807464304

result:

ok single line: '807464304'

Test #27:

score: 0
Accepted
time: 90ms
memory: 3472kb

input:

500
26 2087
39 2091
42 2093
501 2515
57 2096
64 2109
67 2111
71 2112
79 2120
102 2122
111 2124
113 2126
115 2128
115 2129
116 2129
116 2131
119 2141
121 2142
124 2147
130 2149
132 2150
146 2152
148 2154
160 2155
164 2160
164 2162
167 2168
167 2173
168 2173
171 2183
175 2184
176 2186
179 2191
184 219...

output:

689161857

result:

ok single line: '689161857'

Test #28:

score: 0
Accepted
time: 94ms
memory: 3596kb

input:

500
4 1905
7 1916
15 1916
18 1920
943 2914
24 1923
28 1932
37 1948
52 1950
55 1954
56 1959
57 1959
57 1964
63 1978
70 1986
72 1990
74 1991
78 1993
80 1993
81 1997
84 1997
98 2003
116 2003
117 2004
118 2005
120 2008
121 2008
122 2021
128 2028
132 2035
135 2037
138 2039
138 2040
140 2043
140 2053
142 ...

output:

360944141

result:

ok single line: '360944141'

Test #29:

score: 0
Accepted
time: 183ms
memory: 3468kb

input:

500
12 2018
1754 3604
17 2023
19 2026
19 2031
21 2053
25 2056
27 2056
29 2060
29 2069
35 2077
40 2077
44 2089
56 2091
59 2091
60 2095
520 2482
63 2099
67 2105
68 2112
72 2112
81 2123
85 2126
94 2129
105 2131
106 2134
109 2135
115 2135
118 2141
119 2143
123 2144
624 2647
131 2150
141 2151
145 2157
14...

output:

436386241

result:

ok single line: '436386241'

Test #30:

score: 0
Accepted
time: 90ms
memory: 3572kb

input:

500
1 1975
10 1979
19 1980
33 1988
34 1997
34 2002
35 2009
35 2014
36 2016
43 2022
46 2022
47 2024
52 2025
56 2035
59 2039
66 2039
70 2053
70 2053
71 2055
75 2055
79 2056
94 2066
94 2072
96 2072
98 2073
102 2078
114 2080
127 2083
128 2084
130 2093
182 2138
133 2096
135 2098
137 2107
139 2110
141 211...

output:

272725784

result:

ok single line: '272725784'

Test #31:

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

input:

500
257392824 257393039
257206183 257207501
257207498 257209286
257209284 257210501
257210495 257211281
257211277 257211437
257211436 257212063
257212055 257213546
257213545 257215050
257215046 257215525
257215517 257217466
257217457 257218493
257218491 257218680
257218679 257220636
257220633 257220...

output:

741963819

result:

ok single line: '741963819'

Test #32:

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

input:

500
359763520 359764666
359764664 359765010
359765010 359765531
359765530 359766113
359766112 359766300
359766293 359766905
359766901 359768291
359768288 359768361
359768360 359770047
359770040 359771645
359771637 359773274
359773270 359774450
359774446 359776113
359776111 359777764
359777761 359778...

output:

550172424

result:

ok single line: '550172424'

Test #33:

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

input:

500
275094475 275095639
275095639 275095814
275095811 275097717
275097710 275098688
275098685 275098842
275098835 275099017
275099014 275100677
275100674 275101376
275101375 275103362
275103357 275103826
275103821 275105549
275105547 275106688
275106686 275108603
275108596 275108905
275108900 275109...

output:

130181147

result:

ok single line: '130181147'

Test #34:

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

input:

500
339490516 339491326
339491322 339493093
339493090 339495078
339495075 339495504
339495496 339496963
339496957 339497530
339497529 339497806
339497802 339498840
339498835 339500824
339500817 339500999
339500997 339501589
339501586 339502751
339502747 339504539
339504536 339505356
339505351 339505...

output:

423772182

result:

ok single line: '423772182'

Test #35:

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

input:

500
455881331 455881991
455881983 455883495
455883495 455884407
455884400 455885135
455885132 455885654
455885647 455885931
455885930 455887113
455887111 455888483
455888480 455889114
455889111 455891127
455891127 455891500
455891497 455892238
455892237 455894107
455894102 455895008
455895003 455895...

output:

954596898

result:

ok single line: '954596898'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

500
23132758 23136784
22787999 22792740
22316316 22316986
22585370 22588120
23083529 23095626
22379372 22381675
22333301 22334770
22557149 22557978
22411347 22411622
22925200 22929348
22957362 22963815
22465412 22466029
22741689 22743639
22265555 22266080
22919671 22925200
22222222 22223864
22521652...

output:

201460115

result:

ok single line: '201460115'

Test #37:

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

input:

500
22302917 22303387
22837337 22841765
22597675 22597827
22577081 22577708
22861833 22867944
22687464 22689980
22758003 22759386
22556464 22559057
22307353 22309434
22770275 22771281
22559057 22560557
22481171 22483638
22441942 22441975
22524040 22526871
22335380 22336914
22958078 22960136
22947931...

output:

252371564

result:

ok single line: '252371564'

Test #38:

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

input:

500
22526726 22528592
22482585 22484632
22551295 22552329
22318130 22319190
22903057 22904176
22806707 22808570
22310072 22311440
22812916 22817121
22987822 22993227
22961336 22963437
22614312 22617178
22634398 22634756
22291096 22291182
22856257 22859271
22489368 22490312
22820599 22821364
22538217...

output:

68020425

result:

ok single line: '68020425'

Test #39:

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

input:

500
22391177 22393392
22474300 22476662
22550513 22553373
22674877 22678495
22694414 22695550
22535707 22537612
22224832 22225535
22227768 22228993
22600220 22600988
22579945 22582548
22308542 22309754
22367670 22369956
22332855 22333848
22505745 22507602
22811522 22814334
22568139 22569417
22449366...

output:

891271575

result:

ok single line: '891271575'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

500
22932573 22933372
23025447 23034719
22231801 22232122
22615796 22616882
22450819 22450877
22384220 22384829
22952312 22953377
22330798 22332006
22516160 22517109
22663656 22665445
23055040 23058572
22269927 22271309
22703515 22705130
22420777 22421967
22483040 22483296
22853077 22858405
22876894...

output:

802692144

result:

ok single line: '802692144'

Subtask #3:

score: 27
Accepted

Test #41:

score: 27
Accepted
time: 0ms
memory: 3540kb

input:

100
191358459 947004691
342443850 366915813
22574423 36448174
228846908 747282766
190110113 253913299
93029730 879223713
290883541 747723417
162887369 973643964
586349400 863191444
242642824 878391136
18343882 502405347
18658435 174450786
308510413 787915209
79222154 665119810
422422946 793255277
53...

output:

167281196

result:

ok single line: '167281196'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

100
383581393 816569935
148622782 696834692
514001933 750928139
133856778 549893268
514506767 925250706
217782864 954840051
903391822 953609501
29918251 32907029
470521732 690436226
499464782 741535745
787778349 959778964
430781962 497845242
269734667 660122499
580335811 745113176
756807722 87971325...

output:

281268921

result:

ok single line: '281268921'

Test #43:

score: 0
Accepted
time: 3ms
memory: 3380kb

input:

100
47376766 664313233
394991487 987813102
567510996 864092804
474261027 978587193
509899432 901924991
373485619 996550948
38985049 473280384
12721037 440510222
550510929 624405552
302186547 382317878
56742034 999054012
325629327 680836214
207364731 926875891
594450942 770071514
753663655 851754873
...

output:

720025843

result:

ok single line: '720025843'

Test #44:

score: 0
Accepted
time: 4ms
memory: 3476kb

input:

100
298419616 843564930
59305155 297269005
531834796 928938169
441735148 973559139
605818424 621425326
703322783 800904117
539057263 839739855
170044757 374288196
23611398 790255887
47685709 779877820
283057492 638606328
38833997 694366776
178486963 538594252
39641281 342815660
436787994 668729197
8...

output:

826742871

result:

ok single line: '826742871'

Test #45:

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

input:

100
555348798 709755670
168305976 212781628
228849382 744856727
56990747 168240982
787296311 984214458
169406326 917964743
158730667 910083423
12190181 112640248
110033901 995322986
300818828 374776167
233036103 963819115
142239043 570131457
299911077 935341942
584668465 699560602
45776192 885937888...

output:

413352225

result:

ok single line: '413352225'

Test #46:

score: 0
Accepted
time: 18ms
memory: 3464kb

input:

100
4286365 334929271
4981537 338808196
23557681 356699543
33398390 358101339
34707941 358658676
38324357 359183774
95038043 439124352
41048045 360430437
41768720 371264235
287907515 691529451
43996090 376960454
273337618 677267192
199544359 589099362
63243951 403838291
64933918 410238579
43243549 3...

output:

44387135

result:

ok single line: '44387135'

Test #47:

score: 0
Accepted
time: 5ms
memory: 3556kb

input:

100
20024968 371243560
330351675 712369644
23278781 380556271
318072353 701674210
27372590 389713615
27686608 391001475
34068033 394316754
36509231 394786232
322674812 705258749
41512160 397511305
51856814 404987080
319088752 704784719
49917172 401779835
50075615 403955860
48661613 398682628
5406787...

output:

7399403

result:

ok single line: '7399403'

Test #48:

score: 0
Accepted
time: 5ms
memory: 3692kb

input:

100
9198943 369659170
252989538 575101349
19510121 374889661
21431381 384205475
335874543 719411028
24658942 391583394
27093001 398757268
34206074 399439383
35200850 399963001
35890489 401635559
40759287 407411585
342408092 730051987
53733306 416593228
55894064 420964533
309940688 690955410
58876958...

output:

450095995

result:

ok single line: '450095995'

Test #49:

score: 0
Accepted
time: 5ms
memory: 3464kb

input:

100
1706537 371893895
4810220 372381936
340358769 711984953
297035471 662141002
8564434 384377677
19722778 389427013
23072979 391832621
26574110 393971158
32891774 394720943
42403951 402242215
35545896 401021085
38387143 401746251
106247438 444091749
47460907 404447518
48831160 404757697
55888803 40...

output:

888369190

result:

ok single line: '888369190'

Test #50:

score: 0
Accepted
time: 5ms
memory: 3692kb

input:

100
48265690 374587600
10490181 339498659
10924429 341652033
11618636 342565709
22882930 343352180
280917927 711718056
143525633 493359100
28422578 362842787
28596159 363155050
313132775 736801779
26957300 359984482
7994339 337785020
59713146 376376490
62418047 387721020
68395789 390187577
69857186 ...

output:

639276319

result:

ok single line: '639276319'

Test #51:

score: 0
Accepted
time: 4ms
memory: 3680kb

input:

100
1742949 162238200
5430997 752445937
5803156 568237652
11057966 45859889
16561452 908042947
18085991 769134265
18336626 358689120
18795682 348214311
29825242 263584110
31772977 437320451
39282990 600273357
52063839 996154673
431097815 778404392
57718388 619194664
64482635 429954303
75271030 97973...

output:

168347538

result:

ok single line: '168347538'

Test #52:

score: 0
Accepted
time: 3ms
memory: 3444kb

input:

100
1648626 403768768
5159779 392060583
6900671 187788672
13032456 837080381
19967029 113388787
22847858 101380347
433114523 867399222
35420256 249064179
38282907 97140752
105867108 389731175
46520756 568343575
48929133 535156352
60108363 997642539
62426861 368711541
63328425 592452830
68987112 2466...

output:

837057837

result:

ok single line: '837057837'

Test #53:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

100
53206780 701552611
13840621 218491257
330624565 998078904
98973769 911024153
22946200 30809151
30492600 792406354
40153225 599727909
40822332 879404305
194847253 389278992
549204 266820571
53526336 948296016
59300922 822988813
65491195 377325445
66391645 836628006
71305961 98254149
81107245 3736...

output:

741328081

result:

ok single line: '741328081'

Test #54:

score: 0
Accepted
time: 3ms
memory: 3356kb

input:

100
19180936 742907446
30712602 726016511
115465166 974039212
38459157 639067171
803860636 849690860
39601910 254434876
42450831 456754044
93269462 775144162
96854254 824528603
97112505 879493663
109378147 415410035
111527508 375737657
134055587 662135693
117395348 395222066
119507482 207273589
1215...

output:

823390527

result:

ok single line: '823390527'

Test #55:

score: 0
Accepted
time: 3ms
memory: 3432kb

input:

100
1886273 642680910
6943573 931446211
14880352 64904283
103201125 477902958
30417827 546416691
32912079 157983903
39616607 623034286
56184085 85949067
459091897 510735743
57911294 590682791
58719158 333216740
60276280 411143700
346689031 997780767
65168037 700249153
93651140 127966867
94115121 524...

output:

362834974

result:

ok single line: '362834974'

Test #56:

score: 0
Accepted
time: 3ms
memory: 3436kb

input:

100
77671609 272592863
77671609 716914494
27023382 928910161
677153236 902303504
552323605 758630957
27023382 490658992
227579778 675744474
232777649 654222397
138358802 199004231
27023382 569163292
278927405 686537507
27023382 961069802
111671114 624392284
109815537 111671114
114800918 552323605
30...

output:

314359176

result:

ok single line: '314359176'

Test #57:

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

input:

100
192581477 989087814
299989070 611050414
92082640 929372492
119829869 323037264
244304079 849163329
440773553 704128696
884783889 989087814
991317871 996876660
440773553 691765647
405106437 813011908
636839572 708201120
432728824 874829328
179299262 874829328
776054905 923692911
195035122 5180580...

output:

512180893

result:

ok single line: '512180893'

Test #58:

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

input:

100
41487637 487367211
275195437 421488090
710727204 796623144
188296381 205905055
76552075 781934815
172638924 713853296
356278080 587428421
487367211 903535241
172317546 968527813
361033855 871754431
196327571 598825560
125634211 459115700
145591023 180881917
215745786 487367211
135265594 68641951...

output:

396562645

result:

ok single line: '396562645'

Test #59:

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

input:

100
78320887 403473171
572032610 981242610
11978066 791716543
114129022 595561934
177474817 981242610
828535510 969726696
363454560 368689441
437807247 981242610
249869343 527417142
261430050 349760196
727425346 956667128
68733386 909478454
222021776 727046685
317576170 572032610
570121960 572072206...

output:

67963454

result:

ok single line: '67963454'

Test #60:

score: 0
Accepted
time: 3ms
memory: 3416kb

input:

100
259780149 408143598
295251037 615898303
540680082 605229613
105297737 408143598
558572348 913604801
6634559 605229613
567181468 823596652
274912464 474921194
264891697 273354761
295251037 758122576
772619047 787443235
200069291 920935697
105297737 787443235
103695458 199104344
133070258 63987630...

output:

992480862

result:

ok single line: '992480862'

Subtask #4:

score: 42
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #61:

score: 42
Accepted
time: 66ms
memory: 3600kb

input:

500
851440668 951159939
387881127 613157870
93998278 492274255
664765993 836716756
659653974 895584535
204974205 468933806
277201217 636788879
240420920 932252402
8694538 511565691
148542184 636627129
556461249 682742862
815377050 944954653
400020908 520533742
394935657 511747852
305538880 367318828...

output:

186291617

result:

ok single line: '186291617'

Test #62:

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

input:

500
218084335 642361724
126684080 363862754
581542344 589281034
410530895 670487908
171917161 232709890
45382865 739549298
578032348 786521942
674698811 700215529
539895857 649401341
163326805 838051405
695545496 881038786
727379049 905692588
227287000 729002681
110282353 413085219
15609950 40569699...

output:

12136910

result:

ok single line: '12136910'

Test #63:

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

input:

500
173292182 726063470
617485005 979754208
327945446 845344742
95065426 408831073
744874146 939117895
219505883 571536702
620319424 666296797
35118587 302425814
17821378 238646320
75289908 212548335
330829350 951590236
757278455 797063227
375320631 694889235
683407001 954194749
31885996 141768367
1...

output:

901438370

result:

ok single line: '901438370'

Test #64:

score: 0
Accepted
time: 77ms
memory: 3596kb

input:

500
96959114 721679272
388873527 518209465
244499478 892522869
536026274 775212871
243713098 942194638
415141185 530074352
112746066 208006062
809692142 834717768
354932200 739031380
561431825 679783197
354413842 798621159
29520443 644553731
176257389 818953721
983452850 991376160
524960874 91560853...

output:

599796970

result:

ok single line: '599796970'

Test #65:

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

input:

500
624931439 724401192
432867185 616812682
16470026 111027857
690598502 924072970
57118760 835192562
400827375 881648975
174166533 759219895
123075470 554761723
158728073 730436727
18051057 604464751
699162356 781267467
506976027 667507283
52043812 313838158
97329290 473146815
77123728 103258407
31...

output:

406223950

result:

ok single line: '406223950'

Test #66:

score: 0
Accepted
time: 104ms
memory: 3528kb

input:

500
70275 371693882
570790 371990164
3035796 372540461
4414053 373776666
5617265 373843709
5743422 374000023
5816018 377062337
7533202 377235963
7573618 377662389
7712202 377876980
8412923 378510077
9202360 379184095
9987800 379497663
10934800 379562036
11878333 379826515
12040013 381243220
12339550...

output:

351717365

result:

ok single line: '351717365'

Test #67:

score: 0
Accepted
time: 171ms
memory: 3664kb

input:

500
729736 370767975
2231620 371149053
2288939 372469401
3404776 379076522
3564253 379911106
4367832 380018254
5321706 380177111
5646631 380369802
6375037 380642472
6520983 381143764
7452922 381783117
8341525 381940453
9400383 382203307
10404463 382391028
11283295 382633949
12419919 383307087
126970...

output:

165829629

result:

ok single line: '165829629'

Test #68:

score: 0
Accepted
time: 100ms
memory: 3800kb

input:

500
352905 379085200
600400 381084154
861491 381344549
1383462 381588470
1695002 382210349
2196650 382424183
2359343 384262001
2547556 384492456
3047577 384787507
3195854 385483336
3726435 385702222
3991456 385750092
4621417 386304483
6701448 386944380
6803787 388772607
7000191 389991241
7720992 391...

output:

137319555

result:

ok single line: '137319555'

Test #69:

score: 0
Accepted
time: 104ms
memory: 3708kb

input:

500
1675225 369557170
2836091 369750325
2869701 369838188
3380918 371071293
3425998 371091300
3428527 371478163
3791968 374752645
21809575 388454388
8404392 381087425
10112441 381524349
11146222 381962301
12011006 382271494
12558749 382346466
14194745 383200969
14414459 383649433
15196819 385113010
...

output:

642419612

result:

ok single line: '642419612'

Test #70:

score: 0
Accepted
time: 104ms
memory: 3656kb

input:

500
245630 387992612
1806972 388203745
3634120 392194935
4649171 392745566
5694374 393322978
6586820 393592404
8380382 394326653
128580364 505701845
23299624 409761965
10591211 396025301
13220679 396254858
15111745 398073402
15607989 399055007
16339795 399420478
17984813 399420576
18918525 399492621...

output:

760895590

result:

ok single line: '760895590'

Test #71:

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

input:

500
529 992540448
618931 206150834
1061954 66232804
5839872 517219526
5983269 35505561
6557433 123404073
7180532 35755044
361984752 567254319
9892930 369520404
10555114 623151956
11148570 264446901
12185073 64628959
12700121 189335745
14301437 413041295
17074951 323942056
19024427 174278046
19495142...

output:

714815446

result:

ok single line: '714815446'

Test #72:

score: 0
Accepted
time: 61ms
memory: 3612kb

input:

500
1012923 941184633
2343835 300578559
4351415 620228740
5191655 951674812
6367279 581855217
6533694 265439082
7643222 177841418
7867609 267243613
9937318 792860976
14656861 374550331
15959413 177623543
16164294 754563727
16322252 617251881
18289598 652692237
18695989 241168030
18887196 458930570
2...

output:

148576527

result:

ok single line: '148576527'

Test #73:

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

input:

500
83005 398503494
260204 895810192
1474179 274129536
1907933 660406719
2275736 91739254
3134822 62448491
3237514 677826013
3989083 211510498
4393787 958358520
5877532 125153636
6790321 37446085
7805955 523375217
7885047 260699916
8569317 678903680
8577241 570099911
8691265 17939432
11828856 631171...

output:

673737161

result:

ok single line: '673737161'

Test #74:

score: 0
Accepted
time: 61ms
memory: 3544kb

input:

500
1003351 765901035
2673296 856874893
2886060 705226595
3790986 708617430
7314698 122624047
7553267 151870857
10447001 90507933
11319586 638807483
13421616 129902684
13999340 233636432
14719456 488281184
15760474 172626917
20970200 534719020
21713541 574031105
23323551 265402373
23386546 485754258...

output:

689919614

result:

ok single line: '689919614'

Test #75:

score: 0
Accepted
time: 60ms
memory: 3584kb

input:

500
642542 934933733
3354746 184437812
6094168 670136353
6470039 615718936
8698968 132889057
9492671 455450485
10763925 386098428
13881273 519008455
14102971 102922344
14416622 829486618
14752746 667966228
16159711 299814769
16263869 986452355
16634793 132430945
17178349 613741090
17583574 521625180...

output:

830017844

result:

ok single line: '830017844'

Test #76:

score: 0
Accepted
time: 10ms
memory: 3800kb

input:

500
205808516 451346097
470412594 696069181
420735847 812683185
352804737 555342470
291692047 356478084
425555569 689150295
205253397 628265613
94842944 408664393
511064554 892624801
341718641 642731051
145190239 852170571
137526353 511064554
145264863 842588575
551729857 682741844
451614002 6049097...

output:

698098207

result:

ok single line: '698098207'

Test #77:

score: 0
Accepted
time: 13ms
memory: 3448kb

input:

500
61836209 686625091
258482931 852176106
577825245 668325225
176164759 220687770
614762408 644237398
56346422 942407646
61836209 886308584
324428022 810186335
298835420 904082384
875977180 997115954
35172082 200854913
413767572 755155764
810186335 875859525
770455321 904082384
874074138 880601654
...

output:

48652026

result:

ok single line: '48652026'

Test #78:

score: 0
Accepted
time: 13ms
memory: 3604kb

input:

500
457667772 855811880
232784559 507073783
4912688 950398058
588850701 675524294
500631611 810246277
154669439 288120542
507073783 961668235
684348742 949047944
795109197 949047944
135285052 455951445
154669439 855811880
4912688 833199512
461343068 800288081
500631611 787945723
128910010 897910420
...

output:

384495356

result:

ok single line: '384495356'

Test #79:

score: 0
Accepted
time: 14ms
memory: 3508kb

input:

500
751651659 915544886
55536655 676174191
436342385 773549902
436342385 810391996
137016445 505442417
853143155 931658951
369261673 818591783
758896955 891256672
378488861 714905523
915544886 927887847
232963681 643856729
51046075 91971181
86039624 294093634
631147273 991109540
553705867 631147273
...

output:

77540148

result:

ok single line: '77540148'

Test #80:

score: 0
Accepted
time: 16ms
memory: 3596kb

input:

500
273778462 924066200
314166350 929804773
346154110 818228013
116351414 312473009
69331993 185103093
919415954 970330396
541419351 575435933
224336780 225584174
597988619 966438415
234004937 818228013
242553583 687708218
617928809 721747265
13483230 379971710
541419351 768058518
379971710 81600728...

output:

353197380

result:

ok single line: '353197380'