QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448376 | #8035. Call Me Call Me | MEKHANE | AC ✓ | 2537ms | 70408kb | C++14 | 1.1kb | 2024-06-19 15:49:00 | 2024-06-19 15:49:00 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define mid (l+r)/2
using namespace std;
const int N=4e5+5;
int n,B,ans,l[N],r[N],a[N],sum[N],vis[N],bj[N];
vector<int> v[4*N];
queue<int> que;
void ins(int k,int l,int r,int L,int R,int z){
if(L<=l&&r<=R){v[k].push_back(z); return ;}
if(L<=mid) ins(k*2,l,mid,L,R,z);
if(mid<R) ins(k*2+1,mid+1,r,L,R,z);
}
void gx(int k,int l,int r,int wz){
vector<int> v1;
for(auto dq:v[k]){a[dq]--; if(a[dq]>0) v1.push_back(dq); if(a[dq]==0) que.push(dq);}
v[k]=v1;
if(l==r) return ;
if(wz<=mid) gx(k*2,l,mid,wz);
else gx(k*2+1,mid+1,r,wz);
}
void rb(){
rep(i,1,n) sum[i]=sum[i-1]+vis[i];
rep(i,1,n) if(!bj[i]&&a[i]-(sum[r[i]]-sum[l[i]-1])<=B) bj[i]=1,a[i]-=sum[r[i]]-sum[l[i]-1],ins(1,1,n,l[i],r[i],i);
}
signed main(){
ios::sync_with_stdio(false);
cin>>n,B=sqrt(n);
rep(i,1,n){cin>>l[i]>>r[i]>>a[i]; if(!a[i]) bj[i]=1,que.push(i);}
while(!que.empty()){
if(ans%B==0) rb();
int x=que.front(); que.pop(),ans++,vis[x]=1,gx(1,1,n,x);
}cout<<ans;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 47124kb
input:
3 2 3 2 2 3 1 2 2 0
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 3ms
memory: 45480kb
input:
3 2 3 1 2 3 2 2 2 0
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 3ms
memory: 46428kb
input:
50 32 49 11 7 9 3 29 46 2 28 43 14 14 24 12 9 35 26 5 23 5 34 49 7 8 40 28 21 45 19 14 20 8 23 24 0 14 50 9 3 36 12 44 45 2 9 50 2 11 20 8 9 28 17 15 33 0 11 50 21 2 5 2 13 41 27 5 41 18 5 18 2 2 11 1 3 19 9 24 46 9 3 14 13 37 44 5 4 40 23 3 32 6 24 38 13 45 45 1 44 50 0 37 49 0 3 15 12 21 23 3 31 3...
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 47372kb
input:
200 11 196 37 68 186 104 36 55 17 37 180 60 106 149 43 26 67 3 81 140 25 130 136 8 38 118 59 140 187 11 44 66 24 117 145 15 140 147 9 26 105 1 82 107 7 51 66 15 38 113 9 71 89 7 2 87 51 123 127 1 19 24 1 60 177 90 134 153 5 10 125 75 49 60 0 158 185 21 91 165 27 80 199 44 137 173 30 52 127 71 13 40 ...
output:
80
result:
ok 1 number(s): "80"
Test #5:
score: 0
Accepted
time: 7ms
memory: 47100kb
input:
500 62 73 6 80 197 86 424 463 40 34 402 9 288 482 56 358 479 130 120 463 375 156 381 149 237 442 31 136 334 132 23 328 229 243 331 34 241 376 17 29 31 3 130 241 40 70 119 25 179 469 64 400 438 26 137 495 125 247 462 137 76 422 169 49 220 177 177 184 6 95 306 116 62 292 7 120 163 4 311 413 95 263 486...
output:
400
result:
ok 1 number(s): "400"
Test #6:
score: 0
Accepted
time: 3ms
memory: 46656kb
input:
500 374 422 22 220 426 21 389 432 36 289 375 44 220 408 175 181 326 107 41 202 79 57 81 22 249 467 119 465 486 13 169 305 53 56 82 5 78 123 41 146 200 4 168 216 43 198 360 67 52 216 147 188 489 15 172 204 6 32 165 131 259 496 98 94 362 199 12 357 156 382 427 7 341 486 14 99 333 19 104 288 46 11 383 ...
output:
350
result:
ok 1 number(s): "350"
Test #7:
score: 0
Accepted
time: 8ms
memory: 46492kb
input:
1000 302 839 526 517 777 307 375 822 654 253 777 577 105 815 775 297 975 460 115 375 325 104 494 214 196 842 646 297 745 7 156 483 385 379 670 105 536 880 402 159 831 522 18 649 544 85 590 2 239 948 788 112 570 550 311 413 88 744 788 33 130 241 10 28 354 74 21 869 172 294 306 11 58 623 768 39 685 73...
output:
100
result:
ok 1 number(s): "100"
Test #8:
score: 0
Accepted
time: 303ms
memory: 56864kb
input:
400000 131626 262151 44708 33479 241968 596 156448 380747 73026 306027 333202 25023 223679 234561 9636 41148 315180 174749 110638 143248 27373 108072 316650 32460 101258 286892 49767 60238 200451 106857 144354 230616 41442 8975 116525 68828 58197 247012 6720 5643 8825 2602 131228 351692 161752 13415...
output:
40000
result:
ok 1 number(s): "40000"
Test #9:
score: 0
Accepted
time: 808ms
memory: 62012kb
input:
400000 181217 382285 205356 5705 73736 23752 48595 113165 64097 68312 114513 44447 93853 288834 132497 134992 195534 31661 83479 112995 3546 30704 246119 40652 281857 290766 5499 28559 360030 299701 180493 384483 10220 43438 256886 29238 229757 243344 11621 36919 208568 146843 155448 302838 4387 844...
output:
120000
result:
ok 1 number(s): "120000"
Test #10:
score: 0
Accepted
time: 1328ms
memory: 65096kb
input:
400000 117191 164491 15948 484 137917 157790 265247 389104 36514 128495 347689 52466 148140 287177 39902 16682 158712 27455 74903 196155 109486 70192 89056 378 102731 389519 305820 34940 104964 49231 108688 141832 8839 12469 266732 202406 317225 358728 42272 114380 199477 1780 331462 348078 2571 426...
output:
200000
result:
ok 1 number(s): "200000"
Test #11:
score: 0
Accepted
time: 1909ms
memory: 68384kb
input:
400000 56701 153019 5331 126457 159230 1335 176892 192753 1185 68188 209115 16352 136777 190708 8678 13333 181758 332282 356419 368268 1043 328377 396298 29741 49133 327611 7165 9582 297993 2409 5645 121562 12942 152850 321505 759 314206 361734 91071 180080 322089 3295 53071 313313 55349 237779 2819...
output:
280000
result:
ok 1 number(s): "280000"
Test #12:
score: 0
Accepted
time: 2267ms
memory: 69608kb
input:
400000 79659 124493 44197 67032 92654 392 194215 254446 19355 167525 367972 66222 182433 263989 412 173681 327730 60345 177776 286446 45010 22536 359993 307582 361335 362147 301 77438 315590 26255 664 6695 41 112967 215181 98671 37395 68991 29048 137625 245562 84575 27135 261661 166078 83555 208275 ...
output:
360000
result:
ok 1 number(s): "360000"
Test #13:
score: 0
Accepted
time: 2537ms
memory: 69804kb
input:
400000 205732 359260 15904 81204 215404 123104 127321 204688 5027 99708 364389 32536 6929 65734 48619 296821 328806 1780 27967 28722 132 228005 249256 19682 15393 172548 155247 142844 253652 41161 181183 362239 158285 189320 313006 86747 29001 34765 1932 56501 176465 104048 206777 209509 1710 11665 ...
output:
400000
result:
ok 1 number(s): "400000"
Test #14:
score: 0
Accepted
time: 2370ms
memory: 70408kb
input:
400000 20639 82151 9351 212613 295578 11584 175369 322140 70733 50408 299460 4658 103106 282914 25309 98009 131995 2446 275132 353503 40167 302111 349289 26302 120883 237094 49587 195715 232881 14199 203427 300901 40215 21668 147887 56934 62100 195911 106459 112370 154716 19140 49096 196297 57178 19...
output:
400000
result:
ok 1 number(s): "400000"
Test #15:
score: 0
Accepted
time: 2127ms
memory: 68364kb
input:
400000 248074 272805 4848 191635 291142 17325 91322 236351 46493 71017 232953 29283 104441 363018 102748 54206 97510 32695 13630 169462 34568 126403 235414 47253 225359 326923 77035 250142 306422 28967 55311 58521 533 114755 229773 90415 251325 302417 13711 175621 219599 283 8244 266478 103663 54680...
output:
320000
result:
ok 1 number(s): "320000"
Test #16:
score: 0
Accepted
time: 1401ms
memory: 66032kb
input:
400000 111656 174972 36202 244085 286540 1092 67165 245460 108006 61812 100832 33012 100648 349493 64754 49897 112725 8700 69146 318913 33429 248261 278842 21615 56307 56405 2 32989 201139 25499 165852 298574 103732 35128 287161 2173 271155 316235 5098 156772 209768 1528 78203 356006 48738 91545 228...
output:
200000
result:
ok 1 number(s): "200000"
Test #17:
score: 0
Accepted
time: 1358ms
memory: 65220kb
input:
400000 165324 250047 69737 395145 395387 179 39639 162561 95671 130743 230302 83832 29571 172076 131345 276445 393326 44018 334592 354949 10025 175072 206213 4635 33226 326815 10009 7982 357091 261462 361233 390508 11011 218741 286084 3134 46909 260717 76278 343948 394303 34813 38922 280941 139081 1...
output:
200000
result:
ok 1 number(s): "200000"
Extra Test:
score: 0
Extra Test Passed