QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#278775 | #6526. Canvas | Crying | AC ✓ | 220ms | 104152kb | C++17 | 3.6kb | 2023-12-07 20:29:51 | 2023-12-07 20:29:51 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 5e5+10;
typedef array<int,2> pr;
void tomin(int& x,int y){x=min(x,y);}
int T,n,m,l[MAXN],r[MAXN],x[MAXN],y[MAXN],vis[MAXN],tag[MAXN];
vector<int>F,G,H;
vector<pr>e[MAXN],re[MAXN];
queue<int>qu;
int dfn[MAXN],low[MAXN],ins[MAXN],st[MAXN],top,dtot,num;
int scc[MAXN],key[MAXN];
vector<int>o[MAXN];
int to[MAXN],toi[MAXN],deg[MAXN],arr[MAXN];
void link(int u,int v,int id){
//printf("try link %d->%d\n",u,v);
assert(!to[u]);
assert(!tag[id]);
to[u]=v;toi[u]=id;tag[id]=1;
deg[v]++;
}
void tj(int u){
dfn[u]=low[u]=++dtot;ins[u]=1;st[++top]=u;
for(auto [v,id]:e[u]){
if(!dfn[v]){
tj(v);
tomin(low[u],low[v]);
}else if(ins[v])tomin(low[u],low[v]);
}
if(dfn[u]==low[u]){
num++;o[num].clear();
while(1){
int nd=st[top--]; ins[nd]=0;
scc[nd] = num;
o[num].push_back(nd);
if(nd==u)break;
}
}
}
void rdfs(int u){
vis[u]=1;
for(auto [v,id]:re[u])if(!vis[v] && scc[v]==scc[u]){
link(v,u,id);
rdfs(v);
}
}
int ans[MAXN],cur;
void solve(){
cin>>n>>m; F.clear();G.clear();H.clear();
rep(i,1,n){
e[i].clear(),re[i].clear(),vis[i]=deg[i]=to[i]=arr[i]=0;
}
rep(i,1,m){
cin>>l[i]>>x[i]>>r[i]>>y[i]; tag[i] = 0;
if(x[i]==y[i]){
if(x[i]==1)F.push_back(i);
else G.push_back(i),qu.push(l[i]),qu.push(r[i]);
}else{
if(x[i]==1)swap(l[i],r[i]),swap(x[i],y[i]);
re[r[i]].push_back({l[i],i});
}
}
while(qu.size()){ //1,2 -> 2,2
int u=qu.front();qu.pop(); if(vis[u])continue;
vis[u]=1;
for(auto [v,id]:re[u]){
tag[id]=1;
G.push_back(id);
qu.push(v);
}
}
/*
printf("here\n");
rep(i,1,n)cout<<vis[i]<<" ";cout<<endl;
*/
rep(v,1,n)for(auto [u,id]:re[v])if(!tag[id]){
if(!vis[u]){
assert(!vis[v]);
e[u].push_back({v,id});
}else{
F.push_back(id);
}
}
rep(v,1,n)re[v].clear();
rep(u,1,n)for(auto [v,id]:e[u])re[v].push_back({u,id});
//缩点跑scc
rep(i,1,n)dfn[i]=0;top=dtot=num=0;
rep(i,1,n)if(!dfn[i])tj(i);
//
rep(i,1,n)vis[i]=0;
//printf("get %d\n",num);
rep(i,1,num){ //对每个scc找一个关键点,然后内部直接保留dfs的边
key[i]=o[i][0];
for(auto u:o[i]){
for(auto [v,id]:e[u])if(scc[u]^scc[v])key[i]=u;
}
/*
printf("key %d : %d\n",i,key[i]);
for(auto u : o[i])cout<<u<<" ";cout<<endl;
*/
rdfs(key[i]);
for(auto [v,id]:e[key[i]])if(scc[key[i]]^scc[v]){
//printf("link %d->%d\n",key[i],v);
link(key[i],v,id);
break;
}
}
rep(u,1,n)for(auto [v,id]:e[u])if(!tag[id])F.push_back(id);
//对于to集合内的边跑拓扑
rep(i,1,n)if(!deg[i])qu.push(i);
while(qu.size()){
int u=qu.front();qu.pop();
if(to[u]){
int v=to[u];
H.push_back(toi[u]);
deg[v]--;
if(!deg[v])qu.push(v);
}
}
rep(i,1,n)assert(!deg[i]);
//输出方案
cur=0;
for(auto id:F)ans[++cur]=id;
for(auto id:H)ans[++cur]=id;
reverse(G.begin(),G.end());
for(auto id:G)ans[++cur]=id;
assert(cur==m);
//模拟一遍得到答案
rep(i,1,m){
int id=ans[i];
arr[l[id]]=x[id],arr[r[id]]=y[id];
}
int sum=0;
rep(i,1,n)sum+=arr[i];
//
cout<<sum<<"\n";
rep(i,1,m)cout<<ans[i]<<" ";cout<<"\n";
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 71184kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 4 2 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 71180kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
19 13 4 1 3 2 5 7 6 8 11 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 3ms
memory: 69244kb
input:
1 7 5 2 1 6 2 1 2 6 1 1 1 5 1 2 2 7 1 1 1 7 2
output:
8 3 5 2 1 4
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 69208kb
input:
1 7 6 2 1 7 2 2 1 4 2 1 2 4 1 2 1 6 1 1 1 6 2 2 2 6 1
output:
9 4 5 3 1 2 6
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 3ms
memory: 71488kb
input:
1 7 5 5 2 7 1 5 1 6 2 3 2 7 1 3 2 6 1 6 1 7 2
output:
7 3 5 4 2 1
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 7ms
memory: 71248kb
input:
1 7 6 1 2 5 1 2 1 7 2 1 2 7 1 2 2 7 1 1 1 5 2 1 2 3 1
output:
8 1 3 4 5 2 6
result:
ok Correct. (1 test case)
Test #7:
score: 0
Accepted
time: 19ms
memory: 69248kb
input:
2000 15 16 2 2 3 1 12 2 15 1 3 2 9 1 6 2 14 1 2 1 15 2 5 2 6 1 7 1 10 1 9 2 15 1 2 2 3 1 4 2 12 1 2 2 9 1 5 2 8 2 3 2 13 1 12 1 13 2 9 2 13 1 5 1 14 2 15 15 5 2 11 1 1 2 8 1 8 1 15 2 6 2 8 2 8 2 9 1 1 1 6 2 6 1 9 2 2 2 5 1 2 1 10 2 7 2 10 1 1 1 15 2 5 2 15 1 7 1 11 2 1 1 2 1 5 2 9 1 15 14 3 1 5 2 1 ...
output:
23 7 1 9 13 15 5 11 3 10 14 8 2 6 4 16 12 20 14 1 13 10 9 8 12 11 6 15 5 3 2 7 4 21 2 6 11 10 13 3 9 8 12 4 14 7 1 5 18 7 3 9 5 11 1 4 8 13 12 6 10 14 2 21 6 3 2 7 1 18 11 16 9 14 10 13 19 12 5 17 8 4 15 21 3 6 2 9 13 14 11 8 5 7 4 12 10 1 21 3 8 14 1 5 2 11 15 9 7 6 13 4 12 10 19 11 9 3 14 5...
result:
ok Correct. (2000 test cases)
Test #8:
score: 0
Accepted
time: 13ms
memory: 69368kb
input:
2000 15 18 10 1 15 2 10 1 15 2 3 2 13 1 5 1 6 2 2 1 10 2 3 2 5 2 7 1 12 2 2 2 3 1 12 1 13 2 5 2 11 1 7 1 15 2 5 1 15 2 6 1 11 2 2 1 6 1 5 1 10 2 5 2 10 1 2 1 7 2 2 1 15 2 15 17 7 2 15 1 6 2 10 1 3 2 12 1 13 2 14 1 1 1 7 2 6 2 15 1 6 2 13 2 1 2 6 1 10 2 15 1 12 2 15 1 9 1 10 2 13 1 15 2 9 2 12 1 3 1 ...
output:
20 14 3 9 10 11 7 16 2 1 13 18 17 5 15 12 4 8 6 21 17 4 14 13 3 2 11 16 10 9 6 1 15 5 12 8 7 21 1 10 11 8 15 6 16 3 13 5 4 2 17 12 9 18 7 14 19 12 5 3 9 4 13 2 14 8 1 15 11 18 6 10 16 7 17 19 4 14 16 8 9 7 12 10 3 1 11 5 15 13 2 6 21 9 10 11 1 3 6 12 4 7 8 13 5 2 20 6 2 13 8 9 4 1 11 7 10 12 3...
result:
ok Correct. (2000 test cases)
Test #9:
score: 0
Accepted
time: 7ms
memory: 69192kb
input:
5 27 33 18 2 23 1 13 1 23 2 2 1 7 2 4 2 7 1 2 1 4 2 9 1 27 2 26 2 27 1 3 2 11 1 2 1 4 2 12 1 18 2 4 2 7 1 25 2 26 1 12 1 17 2 5 1 27 2 5 2 22 1 13 2 25 1 2 1 4 2 4 2 7 1 2 2 26 1 4 2 7 1 2 2 7 1 2 2 17 1 19 1 26 1 3 2 24 1 11 1 24 2 3 2 24 1 3 1 9 2 18 1 22 2 9 1 11 2 5 2 23 2 12 2 17 1 2 2 7 1 4 2 ...
output:
33 23 6 10 22 8 26 13 25 29 31 27 24 32 21 20 18 11 4 2 17 9 5 3 16 15 19 12 28 7 33 1 14 30 37 22 19 6 20 5 3 10 17 9 14 4 13 21 2 8 16 24 27 26 7 28 25 1 11 18 15 23 12 38 22 15 27 31 35 30 8 26 12 28 14 2 21 24 33 34 25 11 16 20 4 29 32 10 7 9 3 13 23 19 6 18 5 1 36 17 34 32 5 7 30 33 24 23 17...
result:
ok Correct. (5 test cases)
Test #10:
score: 0
Accepted
time: 3ms
memory: 69240kb
input:
5 27 37 10 2 25 2 18 2 22 1 18 1 22 2 2 1 24 2 14 2 26 1 4 1 27 2 15 2 25 1 24 1 27 2 7 2 20 1 11 1 18 1 2 1 14 2 15 1 25 2 10 2 15 1 9 1 16 2 24 2 27 1 24 1 27 2 10 2 12 1 10 1 15 2 9 2 14 1 6 1 15 2 7 1 27 2 24 1 27 2 6 1 22 2 16 1 20 2 15 1 24 2 4 1 27 2 24 1 27 2 2 1 4 2 24 2 27 1 7 1 26 2 24 1 ...
output:
35 10 4 6 26 20 21 17 37 5 23 3 35 36 2 30 28 33 9 24 14 19 11 29 15 32 31 27 22 16 8 34 25 13 12 7 18 1 37 31 32 23 19 11 18 29 28 26 8 7 16 3 21 20 4 25 34 6 14 33 22 15 27 17 13 12 9 2 30 10 24 5 1 35 22 33 23 34 25 10 5 15 32 7 16 31 20 26 14 21 1 6 18 27 19 13 12 24 4 2 8 29 17 11 9 30 3 28 ...
result:
ok Correct. (5 test cases)
Test #11:
score: 0
Accepted
time: 79ms
memory: 71720kb
input:
200 739 1933 110 1 669 2 17 2 403 1 39 1 538 2 36 2 267 1 66 2 259 1 55 2 483 1 245 2 450 1 30 1 729 2 318 1 568 2 344 1 681 2 11 2 37 1 15 2 192 1 55 2 344 1 426 2 596 1 3 2 683 1 499 1 614 1 302 1 367 2 220 1 528 1 223 2 563 1 255 2 719 1 153 2 688 1 371 2 648 1 704 2 715 1 367 2 477 1 451 2 698 2...
output:
1031 16 18 131 172 187 212 295 340 391 397 426 428 430 434 440 555 563 602 618 620 675 694 803 833 837 931 935 954 978 1005 1051 1127 1128 1243 1280 1363 1367 1406 1484 1535 1578 1583 1620 1632 1672 1724 1726 1757 1806 1924 1623 838 1205 483 551 390 160 1195 974 920 178 158 9 1905 1644 1545 1425 957...
result:
ok Correct. (200 test cases)
Test #12:
score: 0
Accepted
time: 70ms
memory: 69640kb
input:
200 748 1673 173 2 219 1 77 1 143 2 19 2 384 1 277 2 371 1 272 2 424 1 203 2 737 1 90 1 129 2 302 1 717 2 527 2 700 1 124 2 673 1 129 2 708 1 546 2 650 1 151 2 689 1 475 2 603 1 173 1 574 2 277 1 605 2 129 2 499 1 373 2 546 1 52 2 66 1 238 1 618 2 373 2 473 1 154 2 244 1 278 1 618 2 112 1 129 2 361 ...
output:
1066 79 146 214 244 255 267 301 386 395 436 439 443 478 486 496 529 530 543 579 589 656 679 684 756 758 791 817 821 855 920 928 945 952 958 963 970 998 1000 1106 1262 1303 1366 1373 1377 1439 1496 1518 1586 1654 1673 1386 1167 847 697 364 314 1458 108 1269 988 584 361 1472 1445 922 235 1216 1184 102...
result:
ok Correct. (200 test cases)
Test #13:
score: 0
Accepted
time: 93ms
memory: 71664kb
input:
200 736 1822 500 2 641 1 91 1 700 2 525 2 576 1 101 2 364 1 304 1 689 2 12 2 636 1 338 2 358 1 15 2 296 1 12 2 123 1 608 1 666 2 135 2 473 1 361 1 667 2 137 2 348 1 381 1 502 2 107 1 277 2 23 1 137 2 262 1 602 2 493 1 573 2 158 2 306 1 137 1 587 2 238 2 682 1 580 2 601 1 364 2 620 1 97 2 403 1 27 1 ...
output:
999 39 86 119 255 344 375 515 516 569 576 635 644 674 780 790 809 825 836 848 891 945 1018 1048 1051 1132 1137 1159 1182 1185 1244 1254 1334 1369 1408 1449 1493 1524 1528 1538 1567 1573 1586 1594 1607 1711 1727 1756 1768 1772 1811 40 1604 16 605 606 632 797 1061 1316 1766 1669 1813 220 389 417 685 7...
result:
ok Correct. (200 test cases)
Test #14:
score: 0
Accepted
time: 74ms
memory: 71640kb
input:
200 745 1668 10 1 215 2 136 2 337 1 528 1 727 2 287 1 314 2 93 1 692 2 37 2 497 1 577 2 597 1 100 1 306 2 313 1 743 2 421 1 597 2 313 1 342 2 236 2 305 1 198 1 617 2 52 1 156 2 144 2 368 1 170 1 428 2 209 1 241 2 125 1 306 2 381 2 715 1 37 1 156 2 395 2 581 1 186 2 580 1 81 1 216 2 120 1 306 2 251 2...
output:
1012 81 94 102 113 152 197 225 248 282 284 286 345 369 379 431 511 521 662 670 701 707 744 757 804 851 861 866 890 905 924 976 1022 1024 1049 1086 1126 1127 1134 1136 1142 1209 1214 1228 1340 1403 1437 1469 1485 1490 1578 1376 1116 929 36 749 108 204 799 1308 879 1416 24 1339 1379 961 1524 145 326 4...
result:
ok Correct. (200 test cases)
Test #15:
score: 0
Accepted
time: 139ms
memory: 78748kb
input:
4 74995 97040 23497 1 31972 2 8788 2 69397 1 51522 2 62220 1 9584 1 11674 2 13370 2 36146 1 39507 1 74477 2 1427 1 33348 2 11493 2 13101 1 32701 2 40560 1 28485 1 47620 2 17874 2 62375 1 20454 2 66633 1 13755 2 61191 1 12861 2 63188 1 52357 1 67165 2 12934 1 59450 2 14794 1 17744 2 61153 1 69340 2 8...
output:
99836 194 1162 1795 3167 3284 3970 5090 7709 12750 13515 15432 15498 16754 16927 20036 20714 23133 27037 27118 28938 31136 31294 31393 31939 33032 36376 36430 39624 40558 41384 42098 42225 42293 42510 42956 43899 44070 44668 45203 47935 48106 48211 49049 50974 52861 52934 55251 55325 56326 56834 584...
result:
ok Correct. (4 test cases)
Test #16:
score: 0
Accepted
time: 131ms
memory: 79536kb
input:
4 74988 97757 6254 1 14126 2 2960 2 7884 1 264 1 26963 2 16894 1 73361 2 40794 2 62973 1 15845 1 45281 2 26578 1 61068 2 14464 2 40449 1 60333 1 73068 2 15459 2 72767 1 44940 2 46205 1 56974 1 65823 2 673 1 12086 2 31184 2 60179 1 924 1 72427 2 22116 2 30494 1 39764 1 50149 2 8984 2 34549 1 47283 1 ...
output:
99896 361 1584 2469 2722 3462 3774 3795 4502 5162 5938 6422 7386 7453 8192 8337 10883 11350 12459 13450 14967 16973 17615 18813 20716 21642 21819 22634 24351 26998 27669 27802 28781 29832 32892 33167 35838 35954 37118 38647 38763 40793 41590 42532 42845 43057 46302 47073 47262 47513 47758 48035 4834...
result:
ok Correct. (4 test cases)
Test #17:
score: 0
Accepted
time: 146ms
memory: 82520kb
input:
2 150000 197734 56160 1 148935 2 14203 2 142849 1 141811 2 149919 1 12846 1 140822 2 32811 2 104214 1 37237 2 73067 1 39554 1 58164 2 17623 1 30566 2 45475 1 88051 2 2948 1 36363 2 121185 1 130780 2 43705 2 139248 1 105491 2 114240 1 22905 2 102102 1 52418 2 85590 1 85614 1 142446 2 145002 2 148378 ...
output:
200477 824 1260 1378 1511 2534 2540 2837 3009 4948 7223 7993 8018 8167 8210 8435 8487 8720 8791 8985 9282 9640 10134 10759 10812 11302 12035 12613 12847 13917 15146 15404 15844 15876 17550 17917 18622 18848 18898 19300 20443 20497 21271 21731 21782 22329 22757 22842 23747 23810 24608 24864 24872 249...
result:
ok Correct. (2 test cases)
Test #18:
score: 0
Accepted
time: 135ms
memory: 82868kb
input:
2 149994 189488 105606 1 132955 2 36574 1 86107 2 101018 2 113530 1 122540 2 143227 1 16632 2 89793 1 25443 1 149904 2 99976 2 136760 1 10596 2 112318 1 84455 1 132258 2 85919 2 93042 1 42680 2 68046 1 60230 2 112109 1 30417 1 79467 2 72216 1 109099 2 24431 2 26346 1 31235 1 109427 2 100973 2 114543...
output:
198916 139 187 603 725 826 901 948 1362 1492 1629 2338 2445 2543 3121 3365 3739 4439 5502 7263 7848 8034 8284 9160 9448 10213 10424 10673 11368 11386 11592 11664 11986 12076 13001 13234 13404 14579 14626 14805 14965 15374 15474 16100 16193 16470 17053 17511 18034 18109 18808 19220 19490 20893 21126 ...
result:
ok Correct. (2 test cases)
Test #19:
score: 0
Accepted
time: 179ms
memory: 92444kb
input:
1 299998 436956 66759 1 261790 2 109661 2 298655 1 46487 1 170884 2 76196 2 124936 1 70653 1 154152 2 187319 1 250381 2 131759 1 133674 2 153676 1 231765 2 95797 1 282385 2 95776 1 187606 2 6703 2 106783 1 251760 2 267115 1 54769 2 192966 1 115099 2 180310 1 192901 2 250903 1 35909 2 295379 1 22399 ...
output:
394765 1312 1353 2474 4017 5159 6031 6250 8062 8981 10175 10907 10987 13019 13119 13441 14451 14873 15068 15458 15954 15980 16482 17223 18097 18176 18183 18812 19466 20611 23576 24090 27599 27713 28487 28518 29074 29234 29495 31197 31650 32288 34575 34695 36631 38654 39983 40491 41397 41410 43692 44...
result:
ok Correct. (1 test case)
Test #20:
score: 0
Accepted
time: 220ms
memory: 94756kb
input:
1 299994 438245 38127 2 88766 1 59431 1 233331 2 225189 2 299437 1 76723 2 250018 1 80328 1 284489 2 135816 2 296190 1 27764 2 225748 1 57528 2 199070 1 60742 1 139855 2 129082 1 134585 2 72351 1 177898 2 6906 1 35622 2 33083 2 135388 1 92785 2 180981 1 102084 2 111670 1 116574 1 276018 2 113641 2 2...
output:
362332 1286 1581 1850 2013 2112 4890 5025 5603 5930 6313 7182 8390 8918 9004 9210 9278 11590 11653 14442 15149 15208 15964 16708 17524 17613 18254 19027 19231 20695 22003 23384 23637 24599 28005 29046 29247 29817 31383 34187 34240 35412 38219 39118 39905 41064 41560 43043 43289 44605 45145 46604 475...
result:
ok Correct. (1 test case)
Test #21:
score: 0
Accepted
time: 174ms
memory: 92564kb
input:
1 299998 498452 39091 2 59969 1 15828 2 270690 1 163349 2 191051 1 42486 1 110810 2 30384 1 223902 2 75185 1 269916 2 56964 2 162885 1 98233 2 196058 1 116601 1 127054 2 85919 1 102077 2 196200 2 214656 1 54709 1 265378 2 87175 1 234557 2 15966 1 21852 2 197173 1 277230 2 48503 2 49594 1 67349 2 242...
output:
400616 718 1314 3855 4040 4239 5545 6566 7335 8193 9454 9636 10126 10521 10907 11185 12321 14367 14688 14800 16368 18000 18564 19213 19663 19665 21811 22053 22183 23007 24694 27659 28158 28397 31783 32465 33094 33649 33679 35255 36623 36715 37101 37707 37848 38651 38960 41855 41876 43798 43858 44277...
result:
ok Correct. (1 test case)
Test #22:
score: 0
Accepted
time: 179ms
memory: 92900kb
input:
1 299995 499550 77642 2 123304 1 18605 1 73000 2 172858 1 248852 2 232126 2 281373 1 42007 2 117419 1 223100 2 257268 1 20588 1 213881 2 221459 2 249009 1 151591 2 176060 1 192169 1 210466 2 33033 1 83266 2 149863 2 281213 1 201519 1 223370 2 166375 1 193359 2 9628 2 156701 1 174303 2 207866 1 24592...
output:
400646 2015 3727 4830 5504 6405 9988 10394 10923 11395 13762 14922 16054 17868 18281 18858 18892 19660 20431 22752 23355 23433 24451 24547 28188 30831 31954 34386 34934 35333 35654 36292 36342 37922 44217 44476 44520 46196 47636 47713 47933 48104 48125 48534 48760 49016 49037 49909 50633 53014 54154...
result:
ok Correct. (1 test case)
Test #23:
score: 0
Accepted
time: 183ms
memory: 104120kb
input:
1 500000 499975 309101 2 498946 1 281120 2 349107 1 196611 1 428634 2 366844 1 454632 2 99985 2 491559 1 463849 2 481265 1 15616 2 149720 1 217051 2 272193 1 170421 2 180431 1 286108 1 319941 2 35639 1 479590 2 119301 2 472138 1 143961 2 234120 1 76549 1 381510 2 308177 2 334281 1 320444 2 467256 1 ...
output:
800360 254 548 578 956 1148 2176 2493 4008 5334 6216 6953 7852 10499 10505 10785 11154 11234 12214 12503 13933 15306 16449 16512 16841 17720 19361 19623 19995 20079 20240 21598 22675 24939 27650 29361 29816 30134 31389 31455 32548 33331 33718 34058 36308 37282 37646 37817 38887 40600 41377 43186 440...
result:
ok Correct. (1 test case)
Test #24:
score: 0
Accepted
time: 209ms
memory: 104152kb
input:
1 500000 499909 166847 2 203459 1 216068 1 237544 2 20036 1 283572 2 307653 1 464166 2 254057 1 287554 2 71599 1 145286 2 41917 1 218529 2 9253 2 472960 1 16916 1 44764 2 139158 2 362692 1 7006 1 462308 2 207592 2 323072 1 38281 1 145367 2 152055 2 258524 1 360540 2 390042 1 199177 1 247048 2 335637...
output:
800362 1813 2020 3696 4152 5322 7486 9384 11102 11523 13378 14192 14378 14385 16927 17460 17552 17669 18530 19599 19843 20040 22285 22352 25419 25480 26089 27486 29569 34989 36194 36569 37632 39217 39491 40168 40487 41267 41301 43439 43515 44106 44970 45799 46929 47176 47311 47409 47416 48007 48482 ...
result:
ok Correct. (1 test case)
Test #25:
score: 0
Accepted
time: 175ms
memory: 92508kb
input:
1 299992 496559 131746 1 232026 2 19016 2 180433 1 64221 1 70241 2 234723 2 260569 1 215594 2 236635 1 50989 2 176563 1 122707 2 278470 1 121505 1 152774 2 50211 2 130736 1 94525 2 281655 1 173141 1 176255 2 1808 2 168157 1 225766 1 247791 2 96263 1 280574 2 87079 1 200248 2 62377 2 87304 1 40727 2 ...
output:
400632 575 1169 1324 1415 3703 4957 6551 6677 9414 10583 11885 12474 14580 15211 15332 15350 15475 17184 17256 18043 19496 21553 23205 23927 24080 24468 25981 27698 28869 30976 32190 34875 36425 37479 41680 41800 42275 43236 43306 43443 43562 44105 44422 45365 46549 47962 49301 49664 50724 53835 539...
result:
ok Correct. (1 test case)
Test #26:
score: 0
Accepted
time: 179ms
memory: 92748kb
input:
1 299989 499616 41124 2 236629 1 1708 2 20000 1 34477 1 34685 2 97 1 78502 2 162521 2 235391 1 937 2 226181 1 158944 1 282924 2 30060 2 98585 1 86033 1 271338 2 220135 1 261253 2 31995 1 91491 2 95080 1 145427 2 80355 2 218928 1 97707 2 187312 1 99043 1 175236 2 100685 1 109409 2 40482 2 216124 1 41...
output:
400613 2672 3788 4652 5048 8361 9613 9992 11879 13829 14122 16129 17273 19682 20420 21641 25706 25756 26898 27255 27276 27573 28809 29004 30858 31019 31042 32158 32432 32816 33352 34031 36543 36696 38459 39980 40590 40810 40996 41651 42412 42474 46090 47892 48573 49292 49610 49858 50237 53574 53629 ...
result:
ok Correct. (1 test case)
Test #27:
score: 0
Accepted
time: 192ms
memory: 104092kb
input:
1 500000 499960 156495 2 222771 1 192943 1 231434 2 52394 2 129100 1 22349 1 286266 2 252684 2 449139 1 49700 2 421137 1 133905 1 189382 2 278790 2 407847 1 155574 2 156461 1 355506 2 449725 1 73782 1 314244 2 39645 2 471881 1 95343 2 321999 1 382747 2 485247 1 24729 1 481479 2 179015 1 488398 2 211...
output:
800381 230 962 1067 1739 3009 4997 7893 11044 13565 14091 14418 14425 15701 16330 19799 19948 22142 22261 22786 23227 23529 24408 24723 29252 31802 34909 35130 35375 35460 37108 37711 40023 40289 40811 41084 41589 42231 42260 42771 43282 43699 44883 45243 45374 48446 49463 49671 50370 51121 51139 53...
result:
ok Correct. (1 test case)
Test #28:
score: 0
Accepted
time: 209ms
memory: 104000kb
input:
1 500000 499907 85402 2 291981 1 247209 2 375781 1 121657 2 393609 1 145810 2 254554 1 278586 1 476600 2 120097 1 305154 2 134366 1 240630 2 126915 2 404476 1 163364 1 458303 2 298699 1 471885 2 60039 2 134949 1 218817 2 223093 1 76531 2 370130 1 124352 2 128371 1 65133 2 113736 1 24905 2 390647 1 4...
output:
800349 729 1697 2985 3622 3796 4809 5493 5633 6213 6855 7954 8289 9456 9493 11762 12008 13506 13704 14129 14400 14567 19480 21057 21790 25567 28343 29180 29222 30898 31446 32950 33457 33583 35705 37998 38903 39861 39870 40807 42223 43071 44638 45974 46282 49506 50324 50501 50644 52324 52694 54488 55...
result:
ok Correct. (1 test case)