QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345152#3160. Cuttingtuanlinh123100 ✓213ms19868kbC++204.5kb2024-03-06 11:15:052024-03-06 11:15:06

Judging History

This is the latest submission verdict.

  • [2024-03-06 11:15:06]
  • Judged
  • Verdict: 100
  • Time: 213ms
  • Memory: 19868kb
  • [2024-03-06 11:15:05]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=100005;
ll a[maxn], b[maxn], c[maxn], d[maxn];

namespace BIT
{
    ll n;
    vector <ll> bit;
    void init(ll sz) {n=sz, bit.assign(n+1, 0);}

    void update(ll l, ll r)
    {
        for (; l<=n; l+=l&(-l)) bit[l]++;
        for (++r; r<=n; r+=r&(-r)) bit[r]--;
    }

    ll query(ll i)
    {
        ll ans=0;
        for (; i; i-=i&(-i)) ans+=bit[i];
        return ans;
    }
};

namespace DSU
{
    ll n;
    vector <ll> pa;
    void init(ll sz) {n=sz, pa.assign(n+1, -1);}

    ll Find(ll i)
    {
        if (pa[i]<0) return i;
        return pa[i]=Find(pa[i]);
    }

    void Union(ll a, ll b)
    {
        a=Find(a), b=Find(b);
        if (a==b) return;
        if (pa[a]>pa[b]) swap(a, b);
        pa[a]+=pa[b], pa[b]=a;
    }
};

namespace SegTree
{
    ll n;
    vector <ll> St, lz;
    void init(ll sz) {n=sz, St.assign(n*4+1, 0), lz.assign(n*4+1, 0);}

    ll Merge(ll a, ll b)
    {
        if (a==-1 || b==-1 || (a>0 && b>0 && a!=b)) return -1;
        if (a==b) return a;
        return a+b;
    }

    void Move(ll i)
    {
        if (!lz[i]) return;
        ll t=lz[i]; lz[i]=0;
        St[i*2]=St[i*2+1]=lz[i*2]=lz[i*2+1]=t;
    }

    void update_ver(ll i, ll Start, ll End, ll idx, ll val)
    {
        if (Start>idx || End<idx) return;
        if (Start==End) {St[i]=val; return;}
        ll mid=(Start+End)/2;
        if (idx<=mid) update_ver(i*2, Start, mid, idx, val);
        else update_ver(i*2+1, mid+1, End, idx, val);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }
    void update_ver(ll idx, ll val) {update_ver(1, 1, n, idx, val);}

    void update_hor(ll i, ll Start, ll End, ll l, ll r, ll val)
    {
        if (Start>r || End<l) return;
        if (l<=Start && End<=r && St[i]!=-1)
        {
            if (St[i]) DSU::Union(val, St[i]), St[i]=lz[i]=val;
            return;
        }
        ll mid=(Start+End)/2;
        if (mid>=l) update_hor(i*2, Start, mid, l, r, val);
        if (mid+1<=r) update_hor(i*2+1, mid+1, End, l, r, val);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }
    void update_hor(ll l, ll r, ll val) {update_hor(1, 1, n, l, r, val);}
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll w, h, n; cin >> w >> h >> n; n+=4;
    long long e=0, v=0;
    vector <ll> cx, cy;
    for (ll i=1; i<=n; i++)
    {
        if (i<=n-4) cin >> a[i] >> b[i] >> c[i] >> d[i];
        if (i==n-3) a[i]=0, b[i]=0, c[i]=w, d[i]=0;
        if (i==n-2) a[i]=0, b[i]=0, c[i]=0, d[i]=h;
        if (i==n-1) a[i]=0, b[i]=h, c[i]=w, d[i]=h;
        if (i==n) a[i]=w, b[i]=0, c[i]=w, d[i]=h;
        cx.pb(a[i]), cx.pb(c[i]), cy.pb(b[i]), cy.pb(d[i]);
        if (a[i]==c[i]) e+=d[i]-b[i], v+=d[i]-b[i]+1;
        else e+=c[i]-a[i], v+=c[i]-a[i]+1;
    }
    sort(cx.begin(), cx.end());
    cx.resize(unique(cx.begin(), cx.end())-cx.begin());
    sort(cy.begin(), cy.end());
    cy.resize(unique(cy.begin(), cy.end())-cy.begin());
    ll kx=cx.size(), ky=cy.size();
    DSU::init(n), SegTree::init(kx), BIT::init(kx);
    vector <vector <pll>> event(ky+2);
    for (ll i=1; i<=n; i++)
    {
        a[i]=lower_bound(cx.begin(), cx.end(), a[i])-cx.begin()+1;
        b[i]=lower_bound(cy.begin(), cy.end(), b[i])-cy.begin()+1;
        c[i]=lower_bound(cx.begin(), cx.end(), c[i])-cx.begin()+1;
        d[i]=lower_bound(cy.begin(), cy.end(), d[i])-cy.begin()+1;
        if (a[i]==c[i]) event[b[i]].pb({0, i}), event[d[i]+1].pb({0, -i});
        else event[b[i]].pb({1, i});
    }
    for (ll i=1; i<=ky+1; i++)
    {
        sort(event[i].begin(), event[i].end());
        for (pll j:event[i])
        {
            if (!j.fi)
            {
                if (j.se>0)
                {
                    SegTree::update_ver(a[j.se], j.se);
                    v+=BIT::query(a[j.se]);
                }
                else
                {
                    SegTree::update_ver(a[-j.se], 0);
                    v-=BIT::query(a[-j.se]);
                }
            }
            else
            {
                SegTree::update_hor(a[j.se], c[j.se], j.se);
                BIT::update(a[j.se], c[j.se]);
            }
        }
    }
    for (ll i=1; i<=n; i++)
        if (DSU::pa[i]<0) e++;
    cout << e-v << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

10 10 10
6 5 6 10
4 0 4 3
3 2 3 10
0 8 2 8
3 8 5 8
0 2 7 2
9 6 9 8
8 2 8 7
5 3 6 3
1 1 7 1

output:

3

result:

ok single line: '3'

Test #2:

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

input:

10 10 10
5 7 8 7
3 3 4 3
0 5 10 5
9 0 9 8
5 2 9 2
2 1 2 7
0 8 8 8
7 0 7 1
2 7 4 7
9 9 10 9

output:

3

result:

ok single line: '3'

Test #3:

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

input:

10 10 15
1 1 4 1
5 8 9 8
4 2 4 3
5 1 5 7
5 1 10 1
9 8 9 10
3 3 3 8
1 0 1 9
9 0 9 5
9 9 10 9
1 9 7 9
2 5 3 5
4 4 4 6
5 4 8 4
1 7 9 7

output:

4

result:

ok single line: '4'

Test #4:

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

input:

100 100 100
31 29 31 83
36 54 36 77
11 16 51 16
20 24 20 82
7 1 7 43
46 14 64 14
77 35 77 94
8 26 82 26
59 43 85 43
55 18 94 18
97 22 97 90
46 61 75 61
78 6 78 20
74 3 74 85
34 93 97 93
87 45 98 45
57 23 82 23
5 58 64 58
55 92 58 92
9 10 9 49
8 5 57 5
17 88 61 88
48 68 48 73
53 51 93 51
7 29 85 29
5...

output:

303

result:

ok single line: '303'

Test #5:

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

input:

100 100 144
47 22 89 22
12 12 12 99
94 21 94 64
83 93 83 98
27 29 78 29
18 43 76 43
19 57 29 57
22 33 22 90
71 61 82 61
27 1 27 100
9 47 56 47
37 34 44 34
32 23 89 23
35 58 89 58
8 78 13 78
97 90 97 91
19 7 39 7
29 27 55 27
80 79 88 79
33 8 76 8
6 48 54 48
46 73 46 97
48 53 61 53
92 52 92 53
10 19 2...

output:

781

result:

ok single line: '781'

Test #6:

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

input:

1000 1000 100
17 471 249 471
196 109 196 958
49 508 319 508
374 994 495 994
816 583 816 903
543 168 975 168
641 405 641 985
675 13 995 13
5 7 795 7
927 44 927 503
997 163 997 205
874 293 907 293
159 131 159 466
214 796 958 796
275 938 908 938
390 30 390 978
527 29 527 511
426 61 799 61
458 820 849 8...

output:

157

result:

ok single line: '157'

Test #7:

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

input:

1000 1000 500
49 222 462 222
177 9 177 400
101 731 622 731
901 278 901 706
383 577 383 776
743 409 743 660
326 552 770 552
819 543 819 931
303 383 324 383
43 153 43 298
597 788 602 788
583 991 771 991
25 35 25 944
839 571 839 660
7 82 7 647
585 379 585 973
77 261 983 261
4 7 351 7
240 214 240 690
69...

output:

6684

result:

ok single line: '6684'

Test #8:

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

input:

1000 1000 1000
885 146 885 416
41 230 41 930
620 29 620 969
634 947 720 947
569 153 575 153
894 252 894 374
215 463 215 960
437 758 669 758
46 968 664 968
86 217 86 737
110 660 850 660
548 574 548 917
229 399 229 864
365 533 706 533
85 509 565 509
206 523 371 523
203 273 848 273
566 415 566 694
391 ...

output:

31514

result:

ok single line: '31514'

Test #9:

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

input:

1000 1000 1000
525 571 525 588
617 830 617 871
399 482 399 505
973 863 978 863
233 274 233 292
899 21 899 69
175 367 219 367
701 938 701 969
681 622 716 622
484 968 492 968
812 108 834 108
708 258 749 258
657 871 678 871
750 452 750 466
606 384 613 384
759 146 759 188
2 949 13 949
140 502 164 502
80...

output:

2

result:

ok single line: '2'

Test #10:

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

input:

1000 1000 1000
966 623 966 966
793 681 793 939
653 827 886 827
216 201 216 478
538 170 755 170
311 800 311 1000
698 211 999 211
93 60 93 300
262 971 573 971
368 461 598 461
442 674 812 674
558 476 803 476
696 997 951 997
771 724 998 724
205 869 510 869
3 124 758 124
235 18 485 18
373 523 373 974
149...

output:

23422

result:

ok single line: '23422'

Test #11:

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

input:

1000 1000 1000
505 365 505 966
230 81 230 775
463 97 463 787
293 808 941 808
72 884 990 884
989 20 989 857
532 182 532 940
428 119 428 857
374 317 993 317
38 908 998 908
273 37 273 942
648 43 648 997
451 349 451 983
174 233 989 233
188 148 962 148
297 13 297 969
100 379 841 379
383 428 993 428
44 61...

output:

136910

result:

ok single line: '136910'

Test #12:

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

input:

1000 1000 500
585 56 585 801
152 785 470 785
273 498 851 498
484 304 703 304
79 731 984 731
774 825 774 865
475 110 727 110
387 768 387 901
564 265 564 866
248 729 974 729
713 55 713 490
632 869 1000 869
235 585 918 585
601 272 928 272
747 177 747 895
695 192 695 966
517 15 517 357
132 571 602 571
8...

output:

20555

result:

ok single line: '20555'

Test #13:

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

input:

1000 1000 1000
377 476 377 567
1 130 1 939
164 183 164 575
801 10 801 178
180 184 180 940
446 16 446 840
398 855 820 855
51 180 51 982
632 105 632 822
78 91 537 91
378 181 378 946
21 655 400 655
275 4 275 955
579 314 579 491
108 589 944 589
841 437 841 911
794 258 794 851
224 31 224 927
473 147 473 ...

output:

100268

result:

ok single line: '100268'

Test #14:

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

input:

1000 100 1000
795 13 795 92
0 13 968 13
243 14 243 82
19 54 1000 54
192 2 192 5
270 38 270 73
133 2 133 3
992 57 992 63
20 4 20 14
381 0 381 35
904 45 904 89
51 1 951 1
480 34 480 62
281 50 281 90
371 26 371 45
113 62 113 65
598 28 598 63
158 84 965 84
537 1 537 96
897 61 897 98
768 12 768 89
762 37...

output:

34510

result:

ok single line: '34510'

Test #15:

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

input:

100 1000 1000
26 732 30 732
15 73 76 73
24 817 97 817
24 431 85 431
72 68 72 972
18 586 45 586
18 970 59 970
73 206 84 206
21 638 100 638
66 58 82 58
25 335 32 335
12 30 12 994
4 895 83 895
7 292 28 292
47 34 47 991
74 389 96 389
8 866 32 866
3 911 51 911
7 757 20 757
24 324 90 324
12 750 99 750
52 ...

output:

34095

result:

ok single line: '34095'

Test #16:

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

input:

980 44 53
399 17 652 17
350 17 368 17
751 14 751 15
204 13 845 13
751 18 751 37
820 1 820 5
239 23 610 23
390 7 390 20
182 2 956 2
428 15 428 25
170 1 490 1
525 38 537 38
48 18 670 18
381 7 783 7
571 7 571 41
63 12 63 14
2 25 2 28
302 32 302 38
888 3 888 20
118 18 118 24
3 23 3 42
68 7 68 9
156 15 3...

output:

21

result:

ok single line: '21'

Test #17:

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

input:

48 733 88
5 70 21 70
4 418 35 418
30 113 30 610
12 496 14 496
21 689 31 689
10 608 32 608
8 137 8 170
18 446 35 446
32 339 32 422
19 43 19 352
5 83 44 83
5 190 5 269
3 730 8 730
38 562 38 670
41 454 46 454
6 365 15 365
23 313 23 433
2 109 5 109
25 21 43 21
26 235 34 235
18 2 18 709
4 699 12 699
6 58...

output:

203

result:

ok single line: '203'

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #18:

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

input:

100 10000 100
20 498 20 7816
47 2646 53 2646
81 7069 95 7069
28 2876 79 2876
55 2100 55 9202
29 933 29 8184
56 706 56 761
90 1536 90 3262
21 499 21 6010
50 3399 50 4116
7 1022 24 1022
8 8045 56 8045
74 7294 74 7841
39 9565 54 9565
2 9502 10 9502
66 4188 86 4188
27 5413 27 6236
57 295 78 295
16 1900 ...

output:

230

result:

ok single line: '230'

Test #19:

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

input:

10000 100 100
1686 48 3729 48
4730 28 4730 85
1103 4 4495 4
1098 32 1098 87
4201 62 4201 90
919 70 919 73
5485 39 5485 54
2312 19 2312 84
146 39 146 64
2929 28 6038 28
1733 41 1733 100
8692 23 8692 97
6998 67 9694 67
6263 51 6263 74
2758 79 5349 79
2210 90 7039 90
8553 15 8553 43
65 26 65 61
4754 36...

output:

154

result:

ok single line: '154'

Test #20:

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

input:

10000 10000 100
7116 1114 7734 1114
6163 4498 6163 7771
3510 1177 3510 7124
9271 4984 9271 9508
3030 3452 9708 3452
2146 8852 2518 8852
623 4445 2657 4445
6177 8816 7356 8816
9091 7045 9091 7265
1019 7784 1019 8257
1368 4576 1569 4576
6681 7866 6681 7880
3737 7688 5479 7688
9758 1263 9758 5175
1979 ...

output:

215

result:

ok single line: '215'

Test #21:

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

input:

10000 10000 1000
4064 1916 4064 6743
6655 518 6655 863
2872 7340 4199 7340
1436 1347 5691 1347
435 6279 1974 6279
6285 3513 8629 3513
3306 5215 3306 8080
5195 8442 6226 8442
3272 4135 7549 4135
8778 392 8778 2936
3386 714 3386 6770
7981 128 7981 3240
2138 343 2138 2401
390 173 3806 173
774 8518 774 ...

output:

26665

result:

ok single line: '26665'

Test #22:

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

input:

10000 10000 1000
8139 3828 8619 3828
8403 2819 8403 2874
5967 9686 6373 9686
8499 1642 8499 1757
9417 5410 9417 6294
3734 6021 3734 6690
4817 4677 4817 4820
1336 8302 1336 8715
9085 9563 9945 9563
8190 6357 8335 6357
8197 965 8816 965
871 3723 1735 3723
3506 7466 4485 7466
2520 7515 2520 8131
7622 8...

output:

79

result:

ok single line: '79'

Test #23:

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

input:

1000000 1000000 1000
390996 740511 901596 740511
310690 166566 684247 166566
508225 705770 508225 967178
281937 545668 281937 788224
335476 936453 404508 936453
610408 24143 610408 465711
429068 144415 429068 469720
684242 144518 684242 498073
60124 566882 60124 894880
558275 641968 675684 641968
99...

output:

25615

result:

ok single line: '25615'

Test #24:

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

input:

1000000 1000000 1000
408791 45133 408791 550292
81017 183437 946973 183437
369494 439156 369494 975971
76408 899008 859959 899008
432332 151028 955558 151028
160199 257738 797897 257738
50482 429341 817088 429341
32000 555203 556868 555203
464392 592142 995721 592142
67567 768417 722721 768417
17556...

output:

99500

result:

ok single line: '99500'

Test #25:

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

input:

1000000000 1000000000 1000
191898538 833162520 191898538 977053326
68241964 73513238 463686068 73513238
634289339 956777290 634289339 981420603
441812450 501382977 853378175 501382977
482865686 938252579 896156122 938252579
170821911 13472171 213659992 13472171
219467504 1609794 219467504 202794640
...

output:

28121

result:

ok single line: '28121'

Test #26:

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

input:

1000000000 1000000000 1000
113639713 202329425 113639713 206135209
355962276 569325480 361483883 569325480
736629594 790094864 736629594 793239890
609763992 553999301 614489587 553999301
663025265 766667362 663145441 766667362
994804379 45145213 999826477 45145213
576771336 71169587 576771336 791506...

output:

1

result:

ok single line: '1'

Test #27:

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

input:

1000000000 1000000000 1000
113639713 202329425 113639713 968747144
355962276 569325480 984767107 569325480
736629594 390094858 736629594 999475257
209763991 553999301 832837515 553999301
63025256 766667362 665246451 766667362
194804372 45145213 982301214 45145213
576771336 71169577 576771336 8085072...

output:

111476

result:

ok single line: '111476'

Test #28:

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

input:

1000000000 1000000000 1000
389865918 174565025 389865918 417858364
66570205 6793510 972313468 6793510
674046422 11838085 674046422 950080270
131697514 457105515 964984370 457105515
594656833 726038292 966618374 726038292
70806371 674458378 678279558 674458378
273109935 258243494 729753310 258243494
...

output:

83565

result:

ok single line: '83565'

Subtask #3:

score: 20
Accepted

Test #29:

score: 20
Accepted
time: 1ms
memory: 3920kb

input:

1000 1000 600
467 160 467 845
10 68 10 101
358 513 358 621
66 671 620 671
351 549 596 549
87 746 87 917
526 145 526 559
118 314 118 868
87 584 373 584
4 117 4 150
801 265 801 416
417 269 417 630
480 144 480 550
945 203 945 768
679 484 679 525
93 342 93 504
954 176 954 270
453 206 453 565
898 668 898...

output:

10525

result:

ok single line: '10525'

Test #30:

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

input:

1000 1000000000 603
601 755190731 601 810458592
934 408413681 934 991509232
677 999530155 815 999530155
168 493643722 673 493643722
471 611014716 471 737416010
297 338288031 560 338288031
359 95457712 359 618830356
526 343959777 881 343959777
925 444786130 925 668860824
514 666804490 514 983701500
6...

output:

9023

result:

ok single line: '9023'

Test #31:

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

input:

1000000000 1000 497
827959903 211 827959903 713
423671814 326 423671814 505
151915634 787 151915634 939
973586233 330 973586233 372
243989833 294 381424364 294
852825911 110 852825911 211
656054851 649 980370982 649
361463145 400 562481084 400
598057245 206 598057245 519
356401865 441 356401865 641
...

output:

6182

result:

ok single line: '6182'

Test #32:

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

input:

1000000000 1000000000 1000
630608407 74813188 630608407 572572115
428810287 713956480 539731989 713956480
640066404 189916304 777953387 189916304
139692089 138020424 436628489 138020424
232274854 245431711 232274854 706217149
76021996 254360470 90280084 254360470
78051453 144768536 78051453 46597063...

output:

7634

result:

ok single line: '7634'

Test #33:

score: 0
Accepted
time: 6ms
memory: 4788kb

input:

1000000000 1000000000 10000
669049628 139158927 669049628 226133259
718482206 453214864 721640027 453214864
922685361 202362178 922685361 269486043
176418025 189329098 176418025 207938401
924551310 799389698 971274232 799389698
913658655 45406740 913658655 115315119
684126650 488289248 684126650 538...

output:

49135

result:

ok single line: '49135'

Test #34:

score: 0
Accepted
time: 75ms
memory: 11140kb

input:

1000000000 1000000000 50000
238613172 391515513 238613172 405815949
228020608 514039210 228020608 525135195
764909506 76206052 767077509 76206052
120043781 289917261 130315212 289917261
838856354 367766371 838856354 377711111
190255664 959215979 190255664 960991962
152573495 152153917 162261418 1521...

output:

23820

result:

ok single line: '23820'

Test #35:

score: 0
Accepted
time: 155ms
memory: 19216kb

input:

1000000000 1000000000 100000
170340118 373306152 170340118 379627430
12604058 168765839 12604058 170795182
20332951 541320438 20332951 549298071
134940794 461595827 134940794 470870367
311164461 197351124 311164461 202291947
421842363 147731250 422869432 147731250
282491926 152715320 282491926 15528...

output:

9721

result:

ok single line: '9721'

Test #36:

score: 0
Accepted
time: 148ms
memory: 19196kb

input:

1000000000 1000000000 100000
648681835 61387068 648681835 61467529
482483617 633133302 490538368 633133302
238416060 954280004 238416060 960579571
971671652 48097001 971671652 52691091
961774046 226207867 961774046 234611274
143188037 361192114 152157365 361192114
631586268 619581854 639748156 61958...

output:

23400

result:

ok single line: '23400'

Test #37:

score: 0
Accepted
time: 136ms
memory: 19340kb

input:

1000000000 1000000000 100000
533066721 267929372 533066721 268068695
478609871 93625392 478609871 94238869
509029333 579208129 509709352 579208129
712522492 727418412 712719154 727418412
272180063 572902914 272180063 573774712
758504262 227729418 759289998 227729418
637434739 129362617 637434739 130...

output:

1

result:

ok single line: '1'

Test #38:

score: 0
Accepted
time: 134ms
memory: 18744kb

input:

1000000000 1000000000 100000
273576603 753501145 273576631 753501145
209049647 751024536 209049647 751024584
730324450 156458455 730324489 156458455
462842489 975962094 462842489 975962116
539789616 391587975 539789616 391588008
443086141 242291883 443086228 242291883
935928542 938420909 935928542 9...

output:

1

result:

ok single line: '1'

Subtask #4:

score: 20
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 20
Accepted
time: 0ms
memory: 3648kb

input:

1000 1000000000 100
7 43968095 7 493960250
65 581131798 548 581131798
15 12649619 15 77997837
344 959585892 972 959585892
678 8808259 678 449415725
4 44620129 866 44620129
609 115927927 609 626151529
3 431983456 861 431983456
187 687914604 977 687914604
4 98243626 131 98243626
488 493990653 669 4939...

output:

639

result:

ok single line: '639'

Test #40:

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

input:

1000000 1000000 1000
811428 912500 811428 991665
0 583719 502962 583719
2310 525304 809207 525304
193824 358688 927465 358688
532369 46265 532369 637135
138984 430381 571563 430381
328070 334913 962852 334913
242230 147447 242230 702740
706573 24895 706573 708315
89767 452569 607448 452569
448339 74...

output:

89987

result:

ok single line: '89987'

Test #41:

score: 0
Accepted
time: 15ms
memory: 4804kb

input:

100000000 100000000 10000
56964231 44114401 85422375 44114401
29008416 13599753 29008416 72382465
10123475 26794348 70000105 26794348
56787892 17187810 56787892 82052282
825051 45077432 96135681 45077432
17336721 887735 17336721 93858206
17971352 4323805 37076674 4323805
46719162 73616239 90393440 7...

output:

8515438

result:

ok single line: '8515438'

Test #42:

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

input:

1000000000 1000000000 10
459921400 660253321 898680159 660253321
444301464 506128346 1000000000 506128346
907456047 610711651 1000000000 610711651
530806362 642900194 530806362 1000000000
0 156940602 12949783 156940602
920340425 75722718 920340425 932040113
8999905 9751201 8999905 477997996
34309696...

output:

2

result:

ok single line: '2'

Test #43:

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

input:

1000000000 1000000000 1000
68867029 56932629 911804386 56932629
939961209 89368354 939961209 950956824
456557378 435620219 626574846 435620219
379741614 137402496 379741614 642396957
397405033 220217437 976369146 220217437
8874520 268530671 361130670 268530671
956446623 174033301 956446623 359426032...

output:

63912

result:

ok single line: '63912'

Test #44:

score: 0
Accepted
time: 206ms
memory: 19480kb

input:

1000000000 1000000000 100000
314060950 456655115 314060950 522301056
477691255 172294068 477691255 605883775
386210933 79188884 386210933 614697589
36152617 115132867 942428819 115132867
825121730 25391591 825121730 611449082
45058912 426144153 598566493 426144153
717644893 403514168 828018736 40351...

output:

870642399

result:

ok single line: '870642399'

Test #45:

score: 0
Accepted
time: 8ms
memory: 4548kb

input:

1000000000 1000000000 10000
0 393840145 1000000000 393840145
945650913 0 945650913 1000000000
0 661852937 1000000000 661852937
0 229060819 1000000000 229060819
0 14513778 1000000000 14513778
717164834 0 717164834 1000000000
0 965526025 1000000000 965526025
31057888 0 31057888 1000000000
142976240 0 ...

output:

25004817

result:

ok single line: '25004817'

Test #46:

score: 0
Accepted
time: 85ms
memory: 11856kb

input:

1000000000 1000000000 100000
0 914079958 1000000000 914079958
0 262062750 1000000000 262062750
63763018 0 63763018 1000000000
577171664 0 577171664 1000000000
0 886545314 1000000000 886545314
0 243553613 1000000000 243553613
0 83259349 1000000000 83259349
875384143 0 875384143 1000000000
104346835 0...

output:

2500061585

result:

ok single line: '2500061585'

Test #47:

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

input:

1000000000 1000000000 100000
1 546791688 1000000000 546791688
240363775 0 240363775 999999997
3 929534253 1000000000 929534253
29921656 0 29921656 999999998
0 172034107 999999999 172034107
3 363937344 1000000000 363937344
1 485349184 999999999 485349184
29633408 0 29633408 999999999
0 835111997 9999...

output:

2499971114

result:

ok single line: '2499971114'

Test #48:

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

input:

1000000000 1000000000 100000
726379710 0 726379710 999999998
804109702 1 804109702 999999999
1 642465132 999999998 642465132
277092354 2 277092354 1000000000
0 457166979 999999998 457166979
877351195 1 877351195 1000000000
317575995 2 317575995 1000000000
1 657364554 999999998 657364554
688387004 0 ...

output:

2499967407

result:

ok single line: '2499967407'

Subtask #5:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #49:

score: 50
Accepted
time: 1ms
memory: 3992kb

input:

1000 1000 1000
681 801 681 913
569 2 733 2
794 372 794 897
230 201 324 201
554 200 554 732
482 310 482 420
138 755 138 782
158 14 684 14
607 25 607 777
114 874 301 874
250 470 745 470
600 49 920 49
9 687 542 687
318 693 653 693
460 191 460 382
834 90 834 865
377 221 377 334
4 362 4 569
275 87 483 87...

output:

30921

result:

ok single line: '30921'

Test #50:

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

input:

1000000000 100 1000
109790116 51 979065423 51
74492854 5 74492854 80
978602949 8 978602949 33
788008170 30 788008170 98
335793055 30 335793055 67
244120440 4 244120440 66
871938225 87 871938225 98
512707155 2 512707155 88
641038954 13 641038954 100
729310952 12 729310952 99
607806171 6 607806171 43
...

output:

25684

result:

ok single line: '25684'

Test #51:

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

input:

100 1000000000 1000
6 265708966 71 265708966
2 346633451 26 346633451
19 381128007 61 381128007
14 512338802 47 512338802
34 244306560 46 244306560
48 19803883 48 890526983
93 71243405 93 841867801
21 36808173 29 36808173
26 83374178 26 997023882
28 90732698 28 995940731
12 983238049 17 983238049
11...

output:

25414

result:

ok single line: '25414'

Test #52:

score: 0
Accepted
time: 85ms
memory: 11180kb

input:

1000000000 1000000000 50000
303138220 847266575 303138220 950033221
839457526 461821928 848092680 461821928
660946353 216430884 660946353 599833585
329661785 706629844 910296738 706629844
40711991 295752815 40711991 415697325
214834805 329330249 707238164 329330249
246027911 815984759 262447109 8159...

output:

69779543

result:

ok single line: '69779543'

Test #53:

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

input:

1000000000 1000000000 50000
290211920 220974096 290211920 225901205
624816731 576124390 631800812 576124390
137536708 906457567 137843395 906457567
214358939 126043662 220877566 126043662
327260604 112527740 330139279 112527740
596451510 303751822 605706670 303751822
578342257 417104628 578342257 41...

output:

823

result:

ok single line: '823'

Test #54:

score: 0
Accepted
time: 93ms
memory: 11376kb

input:

1000000000 1000000000 50000
139495724 79705611 826344175 79705611
364385788 723750851 967551502 723750851
95549923 140263942 95549923 712655785
309332921 505532604 951694296 505532604
857622138 379670766 857622138 921542225
386343451 251912806 386343451 763533802
426631989 316900085 965482454 316900...

output:

228688286

result:

ok single line: '228688286'

Test #55:

score: 0
Accepted
time: 207ms
memory: 19172kb

input:

1000000000 1000000000 100000
335112910 439805512 335112910 940976687
197904802 663301720 274837072 663301720
482210286 741100804 905165867 741100804
298773430 506935596 556289887 506935596
43524542 64424864 43524542 216420377
800143372 606509715 800143372 791752518
467317173 29298267 467317173 77136...

output:

278609425

result:

ok single line: '278609425'

Test #56:

score: 0
Accepted
time: 149ms
memory: 19340kb

input:

1000000000 1000000000 100000
790028408 214603191 793808559 214603191
179164015 131137882 179164015 140411554
54018488 109984340 54018488 113316902
208497773 608314938 208497773 612711188
787196152 537338535 787196152 539790611
820458580 689421217 828718606 689421217
183953287 35193263 183953287 3878...

output:

9725

result:

ok single line: '9725'

Test #57:

score: 0
Accepted
time: 213ms
memory: 19868kb

input:

1000000000 1000000000 100000
651301115 97472951 651301115 998286572
472473394 36684418 984784263 36684418
62149513 260604349 62149513 939739495
299952954 453281689 299952954 999274910
225860775 615160048 821123465 615160048
491695899 497448077 491695899 998568177
74901787 119157897 74901787 64899011...

output:

916553764

result:

ok single line: '916553764'

Test #58:

score: 0
Accepted
time: 193ms
memory: 19320kb

input:

1000000000 1000000000 100000
862411424 228668974 862411424 883932322
474251782 848398633 474251782 849571743
423571304 123028116 443237296 123028116
213341002 301561745 827739133 301561745
208210007 287288041 793959384 287288041
10265048 139038428 746210494 139038428
322289035 690067833 688649717 69...

output:

277014875

result:

ok single line: '277014875'

Test #59:

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

input:

1000000000 1000000000 100000
0 287807717 999999999 287807717
0 985970237 1000000000 985970237
849398924 0 849398924 999999999
0 182894849 999999999 182894849
236473396 1 236473396 1000000000
544482958 1 544482958 1000000000
0 858029242 999999999 858029242
178356966 1 178356966 1000000000
254834671 0...

output:

2500024887

result:

ok single line: '2500024887'

Test #60:

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

input:

1000000000 1000000000 100000
14747610 0 14747610 999999997
712679997 2 712679997 1000000000
419213944 2 419213944 999999998
1 957779745 999999998 957779745
191096694 1 191096694 999999998
1 180620238 1000000000 180620238
0 677185063 999999999 677185063
3 402516536 999999999 402516536
258745405 2 258...

output:

2499951784

result:

ok single line: '2499951784'

Test #61:

score: 0
Accepted
time: 108ms
memory: 12160kb

input:

1000000000 1000000000 100000
100 968244201 1000000000 968244201
705814859 86 705814859 999999997
622994297 23 622994297 999999974
258904658 71 258904658 999999988
27 722569792 999999993 722569792
9 933201150 999999934 933201150
59 301758967 999999995 301758967
593500923 60 593500923 999999984
59 361...

output:

2499861248

result:

ok single line: '2499861248'

Test #62:

score: 0
Accepted
time: 113ms
memory: 12408kb

input:

1000000000 1000000000 100000
761364288 906 761364288 999999957
644 408949571 999999704 408949571
750869098 643 750869098 999999871
322445013 868 322445013 999999944
871636240 631 871636240 999999778
501048544 920 501048544 999999924
312 916120392 999999899 916120392
500 458889665 999999826 458889665...

output:

2499894319

result:

ok single line: '2499894319'

Test #63:

score: 0
Accepted
time: 196ms
memory: 19532kb

input:

1000000000 1000000000 100000
198488448 135846402 198488448 939960811
216575127 882400098 500606342 882400098
881816213 728736705 996114417 728736705
563689512 139061825 563689512 534776642
268709174 156601422 889959871 156601422
389227672 2629736 389227672 707112635
386154600 181453598 840830439 181...

output:

889774540

result:

ok single line: '889774540'

Test #64:

score: 0
Accepted
time: 146ms
memory: 19184kb

input:

1000000000 1000000000 100000
275277325 174795181 275363050 174795181
613858045 830500237 613858045 830789122
771009451 813663971 771964966 813663971
89682524 245275104 90291041 245275104
634725740 786169159 634725740 786706189
329359101 525040793 329538197 525040793
862634148 139672047 862634148 140...

output:

1

result:

ok single line: '1'

Test #65:

score: 0
Accepted
time: 193ms
memory: 19796kb

input:

1000000000 1000000000 100000
247403718 731890754 727333565 731890754
281620669 319118830 281620669 796071287
297163647 22772673 798311047 22772673
487718615 195048985 487718615 859013422
378573203 111738693 897503367 111738693
970932213 368618281 970932213 995695024
735017063 96369033 735017063 8128...

output:

695394202

result:

ok single line: '695394202'

Test #66:

score: 0
Accepted
time: 185ms
memory: 19468kb

input:

1000000000 1000000000 100000
496174645 53878327 496174645 761086918
458034252 845827054 894890341 845827054
222261942 165479104 733410574 165479104
272002057 209621102 272002057 811483523
468273507 109956395 848373771 109956395
255931081 622924699 956173619 622924699
753420420 323195887 753420420 76...

output:

512651341

result:

ok single line: '512651341'

Test #67:

score: 0
Accepted
time: 184ms
memory: 18912kb

input:

1000000000 1000000000 100000
421919576 607949085 514227883 607949085
589455207 112578867 589455207 327129695
428069093 133977581 428069093 792051561
194214463 525357776 215384460 525357776
206155589 239184118 206155589 265058485
159047576 573205100 877804206 573205100
173057987 717229061 173057987 9...

output:

123064033

result:

ok single line: '123064033'

Test #68:

score: 0
Accepted
time: 174ms
memory: 19004kb

input:

1000000000 1000000000 100000
946375404 960061741 946375404 987725529
288186299 329174217 919729330 329174217
932446289 240837483 932446341 240837483
414347351 386786964 622184128 386786964
748838431 396484691 748838465 396484691
938671895 647064799 938671895 647064865
607124976 162194351 607125015 1...

output:

67213607

result:

ok single line: '67213607'

Test #69:

score: 0
Accepted
time: 186ms
memory: 19456kb

input:

1000000000 1000000000 100000
825977120 63553124 825977120 993000617
74065696 209737811 991390456 209737811
502354136 632510370 502354173 632510370
487480224 73423154 487480224 997621258
88502194 930011806 996082053 930011806
709714069 86933881 709714069 989687557
963826256 87667980 963826256 9986063...

output:

937352540

result:

ok single line: '937352540'

Test #70:

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

input:

1000000000 1000000000 100000
401874246 172024103 401874291 172024103
26776320 393856251 950204967 393856251
35959589 433868990 996793172 433868990
761438145 86857313 761438145 998203236
776736552 601067277 776736561 601067277
211505305 203184857 211505305 203184891
451791475 310325602 451791478 3103...

output:

933515254

result:

ok single line: '933515254'

Test #71:

score: 0
Accepted
time: 122ms
memory: 12148kb

input:

1000000000 100 100000
121100279 51 121100279 87
786604791 23 786604791 90
762368860 2 762368860 29
862292605 19 862292605 36
41930295 78 41930295 99
64709411 34 64709411 71
123690402 22 123690402 62
549105958 72 549105958 77
942226919 34 942226919 54
723067407 37 723067407 48
70388739 71 70388739 73...

output:

3382242

result:

ok single line: '3382242'

Test #72:

score: 0
Accepted
time: 102ms
memory: 12196kb

input:

100 1000000000 100000
85 406175530 100 406175530
32 747743363 73 747743363
3 397412596 61 397412596
51 730083749 97 730083749
37 232283928 85 232283928
0 741681818 86 741681818
5 303343322 50 303343322
8 467957133 23 467957133
0 239596342 29 239596342
14 454944325 37 454944325
46 372797567 82 372797...

output:

3386194

result:

ok single line: '3386194'

Extra Test:

score: 0
Extra Test Passed