QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448867#8035. Call Me Call Mewsc2008AC ✓1725ms70828kbC++141.9kb2024-06-20 10:31:572024-08-24 17:55:37

Judging History

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

  • [2024-08-24 17:55:37]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1725ms
  • 内存:70828kb
  • [2024-08-24 17:49:26]
  • hack成功,自动添加数据
  • (/hack/786)
  • [2024-06-20 10:31:57]
  • 评测
  • 测评结果:100
  • 用时:1703ms
  • 内存:70668kb
  • [2024-06-20 10:31:57]
  • 提交

answer

#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
typedef int ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=4e5+9;
ll n,B,L[N],R[N],K[N],sum[N],del[N],vis[N];
vector<ll>tr[N<<2];
queue<ll>q;
void Upd(ll x,ll l,ll r,ll ql,ll qr,ll u){
    if(l>qr||r<ql)return ;
    if(ql<=l&&r<=qr)return tr[x].push_back(u),void();
    ll mid=(l+r)>>1;
    Upd(x<<1,l,mid,ql,qr,u);
    Upd(x<<1|1,mid+1,r,ql,qr,u);
}
void Del(ll x,ll l,ll r,ll u){
    vector<ll>::iterator it=tr[x].begin();
    while(it!=tr[x].end()){
        K[*it]--;
        if(!K[*it]){
            q.push(*it);
        }
        if(K[*it]<=0)it=tr[x].erase(it);
        else it++;
    }
    if(l==r)return ;
    ll mid=(l+r)>>1;
    if(u<=mid)Del(x<<1,l,mid,u);
    else Del(x<<1|1,mid+1,r,u);
}
void Build(){
    rep(i,1,n)sum[i]=sum[i-1]+vis[i];
    rep(i,1,n){
        if(!del[i]&&K[i]-(sum[R[i]]-sum[L[i]-1])<=B){
            del[i]=1;
            K[i]-=(sum[R[i]]-sum[L[i]-1]);
            Upd(1,1,n,L[i],R[i],i);
        }
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read();
    B=sqrt(n);
    rep(i,1,n)L[i]=read(),R[i]=read(),K[i]=read();
    rep(i,1,n){
        if(!K[i])q.push(i);
    }
    ll ans=0;
    while(!q.empty()){
        if(ans%B==0)Build();
        ll u=q.front();q.pop();
        ans++,vis[u]=1,Del(1,1,n,u);
    }
    write(ans);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 45884kb

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: 4ms
memory: 47240kb

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: 0ms
memory: 48348kb

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: 45980kb

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: 8ms
memory: 47076kb

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: 8ms
memory: 45848kb

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: 3ms
memory: 46984kb

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: 194ms
memory: 56992kb

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: 535ms
memory: 62316kb

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: 916ms
memory: 65384kb

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: 1343ms
memory: 68708kb

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: 1535ms
memory: 69836kb

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: 1725ms
memory: 70020kb

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: 1583ms
memory: 70828kb

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: 1473ms
memory: 68644kb

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: 981ms
memory: 66364kb

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: 916ms
memory: 65496kb

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