QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409125#1103. Kunaibachbeo2007100 ✓927ms92380kbC++205.7kb2024-05-11 19:22:422024-05-11 19:22:42

Judging History

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

  • [2024-05-11 19:22:42]
  • 评测
  • 测评结果:100
  • 用时:927ms
  • 内存:92380kb
  • [2024-05-11 19:22:42]
  • 提交

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const long long inf=1e18;
const int mod=998244353;
const int maxn=200005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

int N,H,W,lst[maxn];
int X[maxn],Y[maxn],D[maxn];
map<int,set<pii>> mp[6];

priority_queue<piii,vector<piii>,greater<piii>> pq;

//3->0,2->1,2->3,1->0,2->0,

void add(int d,int x,int y){
    if(D[x]==D[y] || D[x]==2 || D[y]==0) return;
    if(D[x]==3 && D[y]==1) return;
    pq.push({d,{x,y}});
}

void del2(int t,int x,int y,int i){
    auto it = mp[t][x].lower_bound({y,i});
    it=mp[t][x].erase(it);
    if(it!=mp[t][x].end() && it!=mp[t][x].begin()){
        pii b=*it;it--;
        pii a=*it;
        add(b.fi-a.fi,a.se,b.se);
    }
}

void del(int i){
    if(!(D[i]&1)){
        del2(0,Y[i],X[i],i);
        del2(2+D[i]/2,X[i]-Y[i],X[i]+Y[i],i);
        del2(4+D[i]/2,X[i]+Y[i],X[i]-Y[i],i);
    }
    else{
        del2(1,X[i],Y[i],i);
        del2(3-D[i]/2,X[i]-Y[i],X[i]+Y[i],i);
        del2(4+D[i]/2,X[i]+Y[i],X[i]-Y[i],i);
    }
}

int sz;
vector<int> com;
map<int,vector<pii>> cc;
pii tree[4*maxn];
int lazy[4*maxn];

void build(int l,int r,int id){
    tree[id].se=com[r]-com[l-1];
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
}

void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        lazy[id]+=val;
        tree[id].fi+=val;
        return;
    }
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id].fi=min(tree[id<<1].fi,tree[id<<1|1].fi);
    tree[id].se=tree[id<<1].se*(tree[id<<1].fi==tree[id].fi)+tree[id<<1|1].se*(tree[id<<1|1].fi==tree[id].fi);
    tree[id].fi+=lazy[id];
}

void get(int x,int y,int u,int v){
    x=max(min(x,W),1LL);
    y=max(min(y,H),1LL);
    u=max(min(u,W),1LL);
    v=max(min(v,H),1LL);
    if(x>u) swap(x,u);
    if(y>v) swap(y,v);
    //cout << x << ' ' << y << ' ' << u << ' ' << v << '\n';
    cc[x].push_back({y,v});
    cc[u+1].push_back({-y,-v});
    com.push_back(y);
    com.push_back(v+1);
}



void solve(){
    cin >> W >> H >> N;
    for(int i=1;i<=N;i++){
        cin >> X[i] >> Y[i] >> D[i];
        if(D[i]&1) D[i]^=2;
        lst[i]=inf;
        if(!(D[i]&1)){
            mp[0][Y[i]].insert({X[i],i});
            mp[2+D[i]/2][X[i]-Y[i]].insert({X[i]+Y[i],i});
            mp[4+D[i]/2][X[i]+Y[i]].insert({X[i]-Y[i],i});
        }
        else{
            mp[1][X[i]].insert({Y[i],i});
            mp[3-D[i]/2][X[i]-Y[i]].insert({X[i]+Y[i],i});
            mp[4+D[i]/2][X[i]+Y[i]].insert({X[i]-Y[i],i});
        }
    }
    for(int i=0;i<6;i++) for(auto cc:mp[i]){
        pii p={-1,-1};
        for(auto [d,id]:cc.se){
            if(p.se!=-1) add(d-p.fi,p.se,id);
            p={d,id};
        }
    }
    while(!pq.empty()){
        auto [d,p]=pq.top();pq.pop();
        auto [x,y]=p;
        if(lst[x]<d || lst[y]<d) continue;
        if(lst[x]>d){
            lst[x]=d;
            del(x);
        }
        if(lst[y]>d){
            lst[y]=d;
            del(y);
        }
    }
    for(int i=1;i<=N;i++){
        if(D[i]==0) get(X[i],Y[i],X[i]+lst[i]/2,Y[i]);
        if(D[i]==1) get(X[i],Y[i],X[i],Y[i]+lst[i]/2);
        if(D[i]==2) get(X[i],Y[i],X[i]-lst[i]/2,Y[i]);
        if(D[i]==3) get(X[i],Y[i],X[i],Y[i]-lst[i]/2);
    }
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    sz=(int)com.size()-1;
    build(1,sz,1);

    int pre=-1,total=0;
    for(auto v:cc){
        if(pre!=-1){
            int cnt=v.fi-pre;
            pii val=tree[1];
            //cout << val.fi << ' ' << val.se << ' ' << pre << ' ' << v.fi << '\n';
            if(!val.fi) total+=cnt*(H-val.se);
            else total+=cnt*H;
        }
        for(auto [l,r]:v.se){
            int val=(l<0?-1:1);
            l=abs(l);r=abs(r);
            l=lower_bound(com.begin(),com.end(),l)-com.begin()+1;
            r=upper_bound(com.begin(),com.end(),r)-com.begin();
            update(1,sz,1,l,r,val);
        }
        pre=v.fi;
    }
    cout << total << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 12336kb

input:

1000 1000
1000
395 147 2
312 997 3
575 326 1
228 726 0
182 290 3
988 379 1
417 534 2
568 574 2
569 252 1
433 961 2
783 963 2
331 845 3
280 15 0
694 304 1
609 20 3
480 169 0
452 434 1
256 356 1
839 467 2
452 979 2
937 864 2
847 266 3
302 287 2
888 916 2
81 769 1
835 63 2
856 794 0
363 399 1
971 408 0...

output:

351232

result:

ok answer is '351232'

Test #2:

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

input:

1000 1000
1000
613 767 3
847 338 0
65 684 2
305 558 0
518 661 3
853 606 1
726 709 2
74 176 1
441 385 3
815 457 1
546 714 1
847 513 2
328 747 0
587 63 3
77 424 2
886 515 0
8 66 0
212 935 3
247 917 3
602 862 0
125 528 0
942 186 1
230 721 3
927 784 1
12 829 0
619 266 1
48 549 1
724 866 0
496 4 3
245 16...

output:

341331

result:

ok answer is '341331'

Test #3:

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

input:

1000 1000
1000
545 235 1
751 441 2
393 441 0
545 289 1
697 441 2
545 593 3
870 441 2
545 766 3
545 230 1
545 165 1
821 441 2
545 717 3
269 441 0
308 441 0
545 449 3
537 441 0
545 433 1
545 783 3
203 441 0
932 441 2
545 828 3
158 441 0
545 54 1
206 441 0
545 102 1
884 441 2
545 780 3
558 441 2
545 65...

output:

2332

result:

ok answer is '2332'

Test #4:

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

input:

1000 1000
1000
508 691 1
88 522 2
594 543 2
470 667 3
346 543 0
470 817 3
791 746 1
162 543 0
470 235 1
778 543 2
823 413 0
470 316 1
697 543 2
470 770 3
243 543 0
470 568 3
445 543 0
470 518 1
495 543 2
470 574 3
439 543 0
470 512 1
501 543 2
470 773 3
470 241 1
772 543 2
470 845 3
168 543 0
470 33...

output:

91488

result:

ok answer is '91488'

Test #5:

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

input:

987 863
1000
337 215 1
426 724 0
314 667 2
977 322 2
681 134 1
27 692 2
90 217 3
5 813 2
608 3 1
483 845 0
69 367 0
132 659 1
527 22 2
646 191 0
874 248 1
147 643 3
372 483 1
676 272 0
430 95 3
371 693 1
127 545 2
339 791 1
29 282 0
827 454 0
597 279 1
285 649 0
870 581 2
242 196 0
491 192 1
696 386...

output:

304733

result:

ok answer is '304733'

Test #6:

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

input:

1000 1000
1000
134 885 1
99 920 2
853 166 1
820 199 1
715 304 2
291 728 2
255 764 2
541 478 2
670 349 2
777 242 2
739 280 2
643 376 1
502 517 1
966 53 1
543 476 2
889 130 1
179 840 2
469 550 2
278 741 1
24 995 1
377 642 1
412 607 2
569 450 2
882 137 1
190 829 2
252 767 2
709 310 2
780 239 2
144 875 ...

output:

50224

result:

ok answer is '50224'

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 30
Accepted
time: 4ms
memory: 12536kb

input:

1000000000 1000000000
1000
622691628 400169593 1
88321523 864579498 2
112795648 764418241 2
976474352 215796854 2
258309362 109282716 2
934060787 825815025 0
408729475 17576500 3
943696061 482556293 1
103043602 676550999 3
544500840 834560269 3
183652027 316815429 1
739055427 743508143 2
996630440 4...

output:

510718011549

result:

ok answer is '510718011549'

Test #8:

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

input:

1000000000 1000000000
1000
434001832 559301213 3
434001832 429662335 3
406314803 401975306 0
412164945 401975306 0
434001832 380138419 1
455838719 401975306 2
434001832 423812193 3
223723685 401975306 0
434001832 191697159 1
497078106 401975306 2
434001832 465051580 3
370925558 401975306 0
549747261...

output:

2291715446

result:

ok answer is '2291715446'

Test #9:

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

input:

1000000000 1000000000
1000
147530776 854510 0
356276711 182273622 1
892824604 150655760 0
813828732 288023557 3
583960105 913715554 1
475591070 170778890 2
557523961 942932849 3
166190673 551599561 0
557523961 160266273 1
948857249 551599561 2
8062983 470739296 3
190516092 551599561 0
557523961 1845...

output:

88532373705

result:

ok answer is '88532373705'

Test #10:

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

input:

987285921 863112267
1000
470324395 497062190 3
442802251 378184556 2
119175366 201807368 0
245084088 680235591 0
826295561 138094488 0
290415700 329007301 2
632261643 815933349 3
503732803 672359032 2
34697007 348992902 1
568159856 469575045 2
975057489 218287894 2
130254145 246280256 3
732744145 22...

output:

455873598338

result:

ok answer is '455873598338'

Test #11:

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

input:

1000000000 1000000000
1000
909404004 181534702 2
484518608 606420098 1
218950493 871988213 2
97788554 993150152 2
981985048 108953658 2
390063590 700875116 1
123392422 967546284 1
504817801 586120905 2
715878815 375059891 1
807461935 283476771 2
404479489 686459217 1
927014680 163924026 2
996538867 ...

output:

27655301105

result:

ok answer is '27655301105'

Test #12:

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

input:

1000000000 1000000000
1000
773022132 211005023 2
999330973 728414009 3
788418382 315547103 0
74213291 517388927 3
139339190 793167597 2
606888585 830563540 0
245662939 495137437 0
618508496 648877021 0
994049586 698532375 3
93738913 552354689 3
73703171 290803409 0
188618377 11002175 3
225615863 606...

output:

481150067104

result:

ok answer is '481150067104'

Test #13:

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

input:

1000000000 1000000000
1000
50373611 409198926 0
450050051 9522486 1
450050051 329920540 1
529328437 409198926 2
450050051 488477312 3
310559536 409198926 0
450050051 269708411 1
589540566 409198926 2
708880065 409198926 2
450050051 668028940 3
450050051 378587475 1
531468928 409198926 2
450050051 49...

output:

2849288541

result:

ok answer is '2849288541'

Test #14:

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

input:

1000000000 1000000000
1000
541475743 439195694 1
704685352 411213621 0
541475743 919546919 3
166304765 544375941 0
906752610 544375941 2
541475743 909652808 3
176198876 544375941 0
541475743 179099074 1
541475743 527951004 1
557900680 544375941 2
541475743 560800878 3
525050806 544375941 0
541475743...

output:

82091697388

result:

ok answer is '82091697388'

Test #15:

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

input:

987285921 863112267
1000
620654899 592269001 0
206328053 105131334 2
782084021 752936230 2
355537106 844939930 1
547127662 821979369 0
963243497 470643549 1
456481028 293494287 0
165831159 838679760 1
925702991 370974278 1
957200202 324257197 1
865108634 55388141 1
579817096 239998821 0
949015489 28...

output:

467023572658

result:

ok answer is '467023572658'

Test #16:

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

input:

1000000000 1000000000
1000
561552965 495764463 2
359727447 697589981 2
465263943 592053485 1
307483196 749834232 2
365867490 691449938 1
267850805 789466623 2
620210070 437107358 1
221472079 835845349 1
966984578 90332850 2
475247979 582069449 1
733520810 323796618 1
117792475 939524953 1
237987778 ...

output:

25388296783

result:

ok answer is '25388296783'

Test #17:

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

input:

1000000000 1000000000
1000
589070350 565712291 0
841681509 118453997 3
572166871 967138461 1
90211368 483439407 3
10864526 533262968 1
55440450 68740119 0
617768896 862672612 0
450878003 43929623 0
156397810 429014509 0
979080648 599228537 1
403934 38451161 3
56671245 3481843 2
143261911 101701716 2...

output:

508058157318

result:

ok answer is '508058157318'

Test #18:

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

input:

1000000000 1000000000
1000
466098270 174395571 1
708125245 416422546 2
596968012 416422546 2
466098270 547292288 3
335228528 416422546 0
466098270 285552804 1
461470466 416422546 0
466098270 411794742 1
466098270 109040665 1
773480151 416422546 2
466098270 18275921 1
864244895 416422546 2
466098270 ...

output:

4246358023

result:

ok answer is '4246358023'

Test #19:

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

input:

1000000000 1000000000
1000
384004974 137019999 3
407193458 545911984 3
402045605 540764131 0
407193458 583366467 3
364591122 540764131 0
407193458 498161795 1
449795794 540764131 2
407193458 399763196 1
548194393 540764131 2
407193458 681765066 3
266192523 540764131 0
300794280 540764131 0
407193458...

output:

79305870521

result:

ok answer is '79305870521'

Test #20:

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

input:

987285921 863112267
1000
449417196 662604888 1
48678588 632059056 2
565832510 404527588 0
371535183 84765876 1
418652998 562074740 3
424509441 571932395 1
841301064 661029462 0
171112471 233732363 1
88051215 238344145 3
15453742 234243312 0
791809396 803035893 0
435155885 369366223 3
879375615 18995...

output:

463406908716

result:

ok answer is '463406908716'

Test #21:

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

input:

1000000000 1000000000
1000
475820435 547875716 2
167693733 856002418 1
449458888 574237263 1
584420395 439275756 1
988172288 35523863 1
145638022 878058129 1
207966425 815729726 2
847187652 176508499 1
241786495 781909656 2
143034024 880662127 2
800443625 223252526 2
546992626 476703525 2
388497984 ...

output:

41055207693

result:

ok answer is '41055207693'

Subtask #3:

score: 60
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #22:

score: 60
Accepted
time: 523ms
memory: 91412kb

input:

1000000000 1000000000
100000
663138948 732069328 2
335193741 619561225 2
228849515 139776269 1
47212693 115044355 3
524067868 401599143 3
106146261 574234389 0
260875000 717722036 1
385177402 465461017 1
479338005 660429439 1
988699096 62489789 0
615810678 308771211 1
149032461 100977004 2
284770096...

output:

49941362127608

result:

ok answer is '49941362127608'

Test #23:

score: 0
Accepted
time: 418ms
memory: 62920kb

input:

1000000000 1000000000
100000
566759277 849622939 3
250197041 533060703 0
852403088 533060703 2
566759277 818704514 3
281115466 533060703 0
461686928 533060703 0
566759277 427988354 1
671831626 533060703 2
261205453 533060703 0
566759277 686329200 3
413490780 533060703 0
566759277 834722393 3
7781758...

output:

39994458607

result:

ok answer is '39994458607'

Test #24:

score: 0
Accepted
time: 476ms
memory: 69884kb

input:

1000000000 1000000000
100000
856953368 114383681 3
850373774 417536320 2
506532450 913767411 3
164374662 571609623 0
506532450 229451835 1
506532450 428780632 1
710326098 571609623 2
506532450 775403271 3
302738802 571609623 0
506532450 367815975 1
506532450 917862991 3
160279082 571609623 0
5065324...

output:

8477051419311

result:

ok answer is '8477051419311'

Test #25:

score: 0
Accepted
time: 600ms
memory: 91172kb

input:

987285921 863112267
100000
750078204 431759396 3
735927921 507211726 2
89989784 643673044 3
419529415 414174555 2
33229006 645473120 2
609967309 433945778 0
662651640 479263604 2
655506911 566373819 0
882777263 282306898 3
793534435 385460770 0
571911685 35383233 1
346995864 336209314 0
324632383 32...

output:

46150537505050

result:

ok answer is '46150537505050'

Test #26:

score: 0
Accepted
time: 467ms
memory: 37280kb

input:

1027 1039
100000
942 795 2
446 469 1
768 800 0
465 169 0
160 947 1
938 660 0
197 451 1
714 863 1
755 48 1
954 319 0
401 103 2
449 648 3
872 481 3
733 119 0
56 348 3
741 504 1
393 383 1
383 503 1
767 558 1
30 389 3
137 862 2
137 21 1
584 332 2
208 601 0
325 183 2
711 445 2
376 96 3
993 1011 0
158 581...

output:

1054717

result:

ok answer is '1054717'

Test #27:

score: 0
Accepted
time: 852ms
memory: 70556kb

input:

1000000000 1000000000
100000
137117336 890747686 1
384041069 643823953 1
29726055 998138967 2
839700629 188164393 1
812635737 215229285 1
961200055 66664967 1
251616864 776248158 2
786916128 240948894 2
132170385 895694637 1
426773534 601091488 1
425680709 602184313 1
967490803 60374219 2
77959030 9...

output:

476523338176

result:

ok answer is '476523338176'

Test #28:

score: 0
Accepted
time: 561ms
memory: 89840kb

input:

1000000000 1000000000
100000
331703518 86776596 3
177544276 9601214 2
12598004 791367628 2
63210770 81094835 3
395593204 141694514 3
554698126 812410968 0
632980957 85257211 1
217546908 860513619 1
789169877 243427925 2
874040830 109363637 2
542511441 56418963 0
164568978 93456673 1
54932496 5866793...

output:

50126205700926

result:

ok answer is '50126205700926'

Test #29:

score: 0
Accepted
time: 438ms
memory: 62988kb

input:

1000000000 1000000000
100000
276411077 540284323 0
435323848 381371552 1
435323848 625003151 3
350605020 540284323 0
435323848 455565495 1
520042676 540284323 2
212597871 540284323 0
435323848 317558346 1
658049825 540284323 2
789429539 540284323 2
556127521 540284323 2
435323848 661087996 3
3145201...

output:

56095255153

result:

ok answer is '56095255153'

Test #30:

score: 0
Accepted
time: 451ms
memory: 69732kb

input:

1000000000 1000000000
100000
908028273 567997813 2
572250164 903775922 3
236472055 567997813 0
572250164 232219704 1
572250164 718834087 3
9589146 793029080 0
253697107 567997813 0
893767881 523476641 2
572250164 657672629 3
482575348 567997813 0
572250164 478322997 1
572250164 498340484 1
641907493...

output:

8253896297688

result:

ok answer is '8253896297688'

Test #31:

score: 0
Accepted
time: 592ms
memory: 92240kb

input:

987285921 863112267
100000
63453291 200913904 1
262979526 382364396 3
428521173 461559387 3
467523646 301730080 0
808002740 287018347 1
968336984 295959161 0
484002215 718756861 0
152615429 35903007 3
517305584 326269650 3
757241012 94825074 3
352013973 130842840 2
85924038 744905558 2
930086878 158...

output:

46229727046871

result:

ok answer is '46229727046871'

Test #32:

score: 0
Accepted
time: 474ms
memory: 36992kb

input:

1027 1039
100000
511 323 0
956 419 1
81 48 0
933 328 1
25 454 0
54 516 3
503 989 0
322 235 0
377 632 2
695 257 3
849 546 3
173 205 0
867 412 0
137 696 2
959 397 1
750 669 0
746 739 1
29 243 0
560 238 0
751 292 1
371 253 0
600 90 0
982 896 2
234 369 2
302 920 1
628 434 0
225 674 1
384 1009 0
65 813 1...

output:

1055185

result:

ok answer is '1055185'

Test #33:

score: 0
Accepted
time: 839ms
memory: 71132kb

input:

1000000000 1000000000
100000
657870508 354607304 2
491838553 520639259 1
660690262 351787550 2
619582145 392895667 1
33499198 978978614 2
472339933 540137879 2
46473278 966004534 1
580043478 432434334 2
570847844 441629968 1
28596244 983881568 1
37550718 974927094 1
147012064 865465748 1
33560334 97...

output:

507526568312

result:

ok answer is '507526568312'

Test #34:

score: 0
Accepted
time: 569ms
memory: 92380kb

input:

1000000000 1000000000
100000
147751737 294000216 1
19894811 252157555 2
943830141 442958986 3
79208847 899661667 0
267118540 881789885 3
3249991 50587546 3
857603266 305308737 0
49916414 255566222 1
951518102 973910058 0
906866212 156237485 1
469212204 804066715 3
32621846 85936341 0
972578543 62777...

output:

49957015480521

result:

ok answer is '49957015480521'

Test #35:

score: 0
Accepted
time: 407ms
memory: 62804kb

input:

1000000000 1000000000
100000
450108760 547507943 0
451372067 546244636 1
315061883 547507943 0
451372067 411197759 1
110992461 547507943 0
451372067 207128337 1
451372067 544850383 1
454029627 547507943 2
451372067 550165503 3
448714507 547507943 0
451372067 459169093 1
539710917 547507943 2
1133308...

output:

62352343214

result:

ok answer is '62352343214'

Test #36:

score: 0
Accepted
time: 472ms
memory: 69968kb

input:

1000000000 1000000000
100000
93427566 250549170 3
556201946 314045627 1
655446864 413290545 2
556201946 512535463 3
691935514 921503744 1
270001190 563996791 1
556201946 87057833 1
556201946 684775571 3
284716920 413290545 0
36831937 768308238 0
339058170 413290545 0
556201946 196146769 1
773345722 ...

output:

8258222391750

result:

ok answer is '8258222391750'

Test #37:

score: 0
Accepted
time: 549ms
memory: 92056kb

input:

987285921 863112267
100000
706589704 692508905 3
105330061 488033004 3
212269662 113150745 0
483521723 404668293 0
679528076 27113719 1
256691122 818507120 3
695910445 223179768 3
972270856 294067877 3
666939729 635492670 1
629868667 4811189 2
278714736 457231478 1
114174633 11160693 1
860447004 783...

output:

46221255626007

result:

ok answer is '46221255626007'

Test #38:

score: 0
Accepted
time: 472ms
memory: 38000kb

input:

1027 1039
100000
746 684 2
99 227 1
880 315 1
404 37 2
1007 636 0
426 987 3
569 303 3
823 197 0
611 309 3
987 239 2
656 522 2
117 60 3
902 391 0
245 713 1
233 590 0
392 895 0
539 1032 3
650 329 2
780 997 1
631 259 2
449 225 1
412 808 3
394 912 3
567 465 1
997 994 0
978 259 3
138 174 2
559 836 3
34 1...

output:

1056052

result:

ok answer is '1056052'

Test #39:

score: 0
Accepted
time: 834ms
memory: 70868kb

input:

1000000000 1000000000
100000
72121795 956404235 1
977020574 51505456 2
435320669 593205361 1
940806182 87719848 1
741414576 287111454 1
353919550 674606480 1
657585498 370940532 1
218817198 809708832 1
46329130 982196900 1
182264846 846261184 1
274769002 753757028 1
348188854 680337176 1
136709656 8...

output:

407410639854

result:

ok answer is '407410639854'

Test #40:

score: 0
Accepted
time: 618ms
memory: 91668kb

input:

1000000000 1000000000
100000
482034022 897612026 0
941070079 873435725 2
835704386 342496489 0
13466062 382686907 0
129139384 825579395 2
227525924 817159483 3
469914421 562818149 2
39842991 26834347 1
532692214 265409301 2
275795255 827158057 2
432562585 30406943 3
614131928 508434352 1
431401567 2...

output:

49919072427797

result:

ok answer is '49919072427797'

Test #41:

score: 0
Accepted
time: 428ms
memory: 65368kb

input:

1000000000 1000000000
100000
519936637 258601371 1
763550477 502215211 2
519936637 745829051 3
519936637 314313670 1
707838178 502215211 2
519936637 690116752 3
314419743 502215211 0
519936637 805940979 3
216210869 502215211 0
519936637 198489443 1
823662405 502215211 2
519936637 446341185 1
5758106...

output:

44497041760

result:

ok answer is '44497041760'

Test #42:

score: 0
Accepted
time: 462ms
memory: 69892kb

input:

1000000000 1000000000
100000
487637375 302473543 1
591230757 406066925 2
487637375 509660307 3
384043993 406066925 0
439983814 406066925 0
487637375 358413364 1
487637375 580348812 3
313355488 406066925 0
487637375 231785038 1
487637375 774999906 3
118704394 406066925 0
487637375 47369389 1
84633491...

output:

8307354131507

result:

ok answer is '8307354131507'

Test #43:

score: 0
Accepted
time: 560ms
memory: 89868kb

input:

987285921 863112267
100000
856920207 366456602 0
856141785 636238896 3
875178317 664279607 2
421062936 569372632 1
400360177 289739485 0
929518919 538884255 3
693041636 563852973 0
807281019 460388605 2
570659793 657474046 1
31623092 722605609 2
168765880 715590839 0
563737583 4879258 2
89432427 418...

output:

46179682182549

result:

ok answer is '46179682182549'

Test #44:

score: 0
Accepted
time: 432ms
memory: 37976kb

input:

1027 1039
100000
17 190 3
868 463 2
483 978 3
665 636 2
453 132 3
471 137 2
236 572 0
654 922 3
909 601 3
317 469 2
366 1002 0
1007 100 0
359 876 0
1027 486 0
198 353 0
883 720 3
743 171 1
960 199 0
677 837 2
424 988 3
593 439 0
670 323 1
79 155 1
40 869 2
986 62 1
423 773 2
89 202 1
254 835 2
960 3...

output:

1056218

result:

ok answer is '1056218'

Test #45:

score: 0
Accepted
time: 927ms
memory: 69628kb

input:

1000000000 1000000000
100000
391529494 653705763 1
112895171 932340086 1
69191361 976043896 2
375613587 669621670 2
423344051 621891206 1
395156920 650078337 2
514704894 530530363 2
89187694 956047563 2
218294630 826940627 1
484447966 560787291 1
566272299 478962958 2
150647623 894587634 1
501823300...

output:

568892059623

result:

ok answer is '568892059623'

Test #46:

score: 0
Accepted
time: 559ms
memory: 91344kb

input:

1000000000 1000000000
100000
298082241 104835646 2
783420614 115992066 2
619452875 994087848 1
29464139 201253739 0
664720 565674766 2
676077789 55336061 3
842020378 930353323 1
872212497 421886950 0
842524086 995891435 0
308620637 874031904 1
359263348 778054695 2
482184796 353430372 1
201563967 26...

output:

49997496156308

result:

ok answer is '49997496156308'

Test #47:

score: 0
Accepted
time: 440ms
memory: 63820kb

input:

1000000000 1000000000
100000
621949231 509438831 2
535984856 595403206 3
450020481 509438831 0
535984856 748931728 3
296491959 509438831 0
535984856 269945934 1
775477753 509438831 2
212814334 509438831 0
535984856 186268309 1
859155378 509438831 2
535984856 832609353 3
888262491 509438831 2
5359848...

output:

51467675232

result:

ok answer is '51467675232'

Test #48:

score: 0
Accepted
time: 470ms
memory: 68420kb

input:

1000000000 1000000000
100000
877374451 447747847 2
537306871 787815427 3
197239291 447747847 0
537306871 107680267 1
96524692 38329019 2
537306871 571807462 3
413247256 447747847 0
537306871 323688232 1
296105175 321071697 1
456170269 447747847 0
537306871 366611245 1
618443473 447747847 2
663317426...

output:

8314959264748

result:

ok answer is '8314959264748'

Test #49:

score: 0
Accepted
time: 574ms
memory: 91504kb

input:

987285921 863112267
100000
685682505 858051603 1
698492320 741907504 3
658926806 315870965 3
437061013 251051732 1
271885513 29834856 0
390784863 198319947 3
904949866 68275881 3
639650525 718553474 2
720293938 524843912 3
77162553 632591723 0
95466643 178867210 3
419076373 134246660 1
19792554 7440...

output:

46246375985396

result:

ok answer is '46246375985396'

Test #50:

score: 0
Accepted
time: 464ms
memory: 38052kb

input:

1027 1039
100000
314 212 3
610 176 2
139 78 1
871 719 3
872 144 3
569 843 2
876 325 1
431 608 3
233 893 0
729 177 2
76 965 3
869 140 1
897 322 0
729 774 3
162 639 3
401 544 3
946 349 3
296 69 1
573 678 0
271 678 0
683 654 3
875 878 3
791 437 2
593 756 2
974 170 2
894 248 1
1013 752 0
976 311 0
914 9...

output:

1056041

result:

ok answer is '1056041'

Test #51:

score: 0
Accepted
time: 847ms
memory: 70464kb

input:

1000000000 1000000000
100000
900809794 96891967 1
784333884 263748228 2
62490464 985591648 2
394104818 653977294 1
140915959 907166153 2
371979024 676103088 2
397315321 650766791 2
593864142 454217970 1
132770431 915311681 2
90101153 957980959 2
148971227 899110885 2
366020012 682062100 1
246652823 ...

output:

442226775128

result:

ok answer is '442226775128'

Test #52:

score: 0
Accepted
time: 558ms
memory: 91492kb

input:

1000000000 1000000000
100000
114130459 459542914 0
625771149 506032054 2
403201364 645679206 2
45462216 167304219 1
19673704 305770137 2
124629654 293512640 3
66642687 150404850 0
704582003 964423200 0
4872310 726373568 1
193962371 68389400 3
285964111 525702446 1
497721312 345910041 0
119210014 451...

output:

50026483129307

result:

ok answer is '50026483129307'

Test #53:

score: 0
Accepted
time: 446ms
memory: 65184kb

input:

1000000000 1000000000
100000
880347982 516662451 2
552033074 844977359 3
223718166 516662451 0
260948820 516662451 0
511208921 516662451 0
552033074 475838298 1
592857227 516662451 2
551203570 516662451 0
552033074 515832947 1
552862578 516662451 2
552033074 517491955 3
161088697 516662451 0
5520330...

output:

48456523650

result:

ok answer is '48456523650'

Test #54:

score: 0
Accepted
time: 459ms
memory: 70228kb

input:

1000000000 1000000000
100000
586976368 613454196 3
410434589 436912417 0
586976368 260370638 1
441580536 436912417 0
586976368 291516585 1
732372200 436912417 2
586976368 510749759 3
513139026 436912417 0
363698989 436912417 0
586976368 213635038 1
810253747 436912417 2
56092008 280721376 3
63821858...

output:

8303589567989

result:

ok answer is '8303589567989'

Test #55:

score: 0
Accepted
time: 598ms
memory: 91508kb

input:

987285921 863112267
100000
170295294 135611110 1
383193391 511391566 3
226423785 40312796 2
469057167 35669044 2
14936185 794396980 3
127690867 400897638 2
514392211 382087116 2
304389537 793030060 1
205188114 701436798 1
982615590 10710799 1
936154090 811050446 1
302665757 834834616 3
694886922 110...

output:

46287075850758

result:

ok answer is '46287075850758'

Test #56:

score: 0
Accepted
time: 469ms
memory: 37572kb

input:

1027 1039
100000
612 757 0
352 412 2
823 741 2
105 280 3
263 678 2
614 1032 2
542 594 2
262 294 2
531 147 0
113 407 1
813 406 1
731 696 2
355 807 0
431 23 2
73 402 2
891 884 2
123 527 1
660 978 3
470 518 2
118 367 1
827 869 2
106 393 1
476 203 0
66 120 3
963 800 3
393 762 3
964 780 3
617 310 2
867 5...

output:

1055250

result:

ok answer is '1055250'

Test #57:

score: 0
Accepted
time: 817ms
memory: 70464kb

input:

1000000000 1000000000
100000
652150584 446262032 1
811568386 286844230 1
492561855 605850761 1
529235491 569177125 2
457816600 640596016 2
811866735 286545881 1
124118847 974293769 2
306463912 791948704 1
236825069 861587547 1
275085394 823327222 1
521054302 577358314 1
812388055 286024561 1
8163039...

output:

614169021291

result:

ok answer is '614169021291'