QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879079 | #8035. Call Me Call Me | sz051 | ML | 7639ms | 1013780kb | C++20 | 2.8kb | 2025-02-01 20:53:56 | 2025-02-01 20:53:57 |
Judging History
This is the latest submission verdict.
- [2025-02-06 18:39:16]
- hack成功,自动添加数据
- (/hack/1529)
- [2025-02-01 20:53:56]
- Submitted
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <stack>
#include <random>
#include <map>
#define int long long
using namespace std;
void read(int &x){
x=0;
int f=1;
char c=getchar();
while(!('0'<=c && c<='9')){
if(c=='-'){
f=-1;
}
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
int lg(int k){
return k==0?-1:__lg(k);
}
struct Alarm{
int qlim[1100010],qh[1100010],delt[1100010],qcnt=0;
vector<int> qp[1100010];
vector<int> seps[1100010][20];
int sum[1100010];
Alarm(){}
int insert(vector<int> pos,int lim){
qlim[++qcnt]=lim;
// printf("[+%lld]:",qcnt);
// for(int i:pos){
// printf("%lld ",i);
// }
// putchar('\n');
qp[qcnt]=pos;
qh[qcnt]=20;
while(qh[qcnt]>=0){
int cur=0;
for(int i:pos){
cur+=sum[i]|((1ll<<qh[qcnt])-1);
}
if(cur>=lim){
qh[qcnt]--;
}else{
break;
}
}
for(int i:pos){
seps[i][qh[qcnt]+1].push_back(qcnt);
}
return qcnt;
}
vector<int> update(int k,int v){
vector<int> res;
int tp=lg(sum[k]^(sum[k]+v));
sum[k]+=v;
for(int p=-1;p<=tp;p++){
vector<int> tmp=seps[k][p+1];
seps[k][p+1].clear();
for(int i:tmp){
//printf("[%lld %lld %lld]",k,p,i);
if(qh[i]!=p){
continue;
}
while(qh[i]>=0){
int cur=0;
for(int j:qp[i]){
cur+=sum[j]|((1ll<<qh[i])-1);
}
if(cur>=qlim[i]){
qh[i]--;
}else{
break;
}
}
if(qh[i]==-1){
res.push_back(i);
}else{
if(qh[i]==p){
seps[k][p+1].push_back(i);
}else{
for(int j:qp[i]){
seps[j][qh[i]+1].push_back(i);
}
}
}
}
}
return res;
}
} alarm;
int n;
vector<int> cur;
void update(int k,int curl,int curr,int ql,int qr){
if(ql<=curl && curr<=qr){
cur.push_back(k);
}else{
int mid=(curl+curr)>>1;
if(ql<=mid){
update(k*2,curl,mid,ql,qr);
}
if(mid<qr){
update(k*2+1,mid+1,curr,ql,qr);
}
}
}
void query(int k,int curl,int curr,int pos){
cur.push_back(k);
if(curl!=curr){
int mid=(curl+curr)>>1;
if(pos<=mid){
query(k*2,curl,mid,pos);
}else{
query(k*2+1,mid+1,curr,pos);
}
}
}
signed main(){
read(n);
int l,r,v;
vector<int> tmp;
int res=0;
for(int i=1;i<=n;i++){
read(l);
read(r);
read(v);
if(!v){
tmp.push_back(i);
alarm.qcnt++;
continue;
}
update(1,1,n,l,r);
alarm.insert(cur,v);
cur.clear();
}
while(tmp.size()){
res+=tmp.size();
vector<int> nw;
for(int i:tmp){
cur.clear();
query(1,1,n,i);
for(int j:cur){
vector<int> vt=alarm.update(j,1);
for(int p:vt){
nw.push_back(p);
}
}
}
tmp=nw;
}
printf("%lld",res);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 56ms
memory: 548556kb
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: 54ms
memory: 550660kb
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: 62ms
memory: 546252kb
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: 57ms
memory: 550568kb
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: 60ms
memory: 545604kb
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: 53ms
memory: 550856kb
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: 54ms
memory: 548684kb
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: 2056ms
memory: 782036kb
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: 4138ms
memory: 877068kb
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: 6354ms
memory: 965824kb
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: 7639ms
memory: 1013780kb
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: -100
Memory Limit Exceeded
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