QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409125 | #1103. Kunai | bachbeo2007 | 100 ✓ | 927ms | 92380kb | C++20 | 5.7kb | 2024-05-11 19:22:42 | 2024-05-11 19:22:42 |
Judging History
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'