1515.md (17666B)
1 Source: https://codeforces.com/blog/entry/90236 2 3 [1515A - Phoenix and Gold](/contest/1515/problem/A "Codeforces Global Round 14") 4 5 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 void solve(){ 18 int n,x; 19 int w[101]; 20 cin>>n>>x; 21 int sum=0; 22 for (int i=0;i<n;i++){ 23 cin>>w[i]; 24 sum+=w[i]; 25 } 26 //if the sum is x, we cannot avoid the explosion 27 if (sum==x){ 28 cout<<"NO"<<endl; 29 return; 30 } 31 cout<<"YES"<<endl; 32 //otherwise, the answer always exists 33 //we will keep adding elements from left to right 34 //if we can't add element i, we add element i+1 first by swapping the two 35 for (int i=0;i<n;i++){ 36 if (x==w[i]){ 37 //i+1 will always be less than n because otherwise, the total sum would be x 38 swap(w[i],w[i+1]); 39 } 40 cout<<w[i]<<' '; 41 x-=w[i]; 42 } 43 cout<<endl; 44 return; 45 } 46 47 int main(){ 48 int T; cin>>T; 49 while (T--) 50 solve(); 51 return 0; 52 } 53 ``` 54 55 [1515B - Phoenix and Puzzle](/contest/1515/problem/B "Codeforces Global Round 14") 56 57 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution** 64 65 ``` 66 #include <bits/stdc++.h> 67 using namespace std; 68 69 bool isSquare(int x){ 70 int y=sqrt(x); 71 return y*y==x; 72 } 73 74 void solve(){ 75 int n; 76 cin>>n; 77 if (n%2==0 && isSquare(n/2)) 78 cout<<"YES"<<endl; 79 else if (n%4==0 && isSquare(n/4)) 80 cout<<"YES"<<endl; 81 else 82 cout<<"NO"<<endl; 83 } 84 85 int main(){ 86 int t; cin>>t; 87 while (t--) 88 solve(); 89 } 90 ``` 91 92 [1515C - Phoenix and Towers](/contest/1515/problem/C "Codeforces Global Round 14") 93 94 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 106 int N,M,X; 107 int H[100001]; 108 109 void solve(){ 110 cin>>N>>M>>X; 111 cout<<"YES"<<endl; 112 set<pair<int,int>>s; //stores pairs of (height, index) 113 for (int i=1;i<=M;i++) 114 s.insert({0,i}); 115 for (int i=0;i<N;i++){ 116 cin>>H[i]; 117 pair<int,int>p=*s.begin(); 118 s.erase(p); 119 cout<<p.second<<' '; 120 s.insert({p.first+H[i],p.second}); 121 } 122 cout<<endl; 123 } 124 125 int main(){ 126 int T; cin>>T; 127 while (T--) 128 solve(); 129 } 130 ``` 131 132 [1515D - Phoenix and Socks](/contest/1515/problem/D "Codeforces Global Round 14") 133 134 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution** 141 142 ``` 143 #include <bits/stdc++.h> 144 using namespace std; 145 146 int N,L,R; 147 int C[200001]; 148 int lcnt[200001],rcnt[200001]; 149 150 void solve(){ 151 cin>>N>>L>>R; 152 for (int i=1;i<=N;i++){ 153 lcnt[i]=0; 154 rcnt[i]=0; 155 } 156 for (int i=1;i<=N;i++){ 157 cin>>C[i]; 158 if (i<=L) 159 lcnt[C[i]]++; 160 else 161 rcnt[C[i]]++; 162 } 163 //remove pairs that are already matching 164 for (int i=1;i<=N;i++){ 165 int mn=min(lcnt[i],rcnt[i]); 166 lcnt[i]-=mn; 167 rcnt[i]-=mn; 168 L-=mn; 169 R-=mn; 170 } 171 if (L<R){ 172 swap(lcnt,rcnt); 173 swap(L,R); 174 } 175 //now, there are at least as many left socks as right socks 176 int ans=0; 177 for (int i=1;i<=N;i++){ 178 int extra=L-R; //always even 179 int canDo=lcnt[i]/2; 180 int Do=min(canDo*2,extra); 181 //turn "Do"/2 left socks of color i into right socks 182 ans+=Do/2; 183 L-=Do; 184 } 185 //turn extra lefts into rights, then adjust all colors 186 ans+=(L-R)/2+(L+R)/2; 187 cout<<ans<<endl; 188 } 189 int main() 190 { 191 ios_base::sync_with_stdio(0);cin.tie(0); 192 int T; cin>>T; 193 while (T--) 194 solve(); 195 return 0; 196 } 197 ``` 198 199 [1515E - Phoenix and Computers](/contest/1515/problem/E "Codeforces Global Round 14") 200 201 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Solution** 208 209 ``` 210 #include <bits/stdc++.h> 211 using namespace std; 212 typedef long long ll; 213 ll MOD; 214 215 int N; 216 ll dp[405][405]; 217 218 ll fastexp(ll b, ll exp){ 219 if (exp==0) 220 return 1; 221 ll temp=fastexp(b,exp/2); 222 temp=(temp*temp)%MOD; 223 if (exp%2==1) 224 temp*=b; 225 return temp%MOD; 226 } 227 228 ll fact[405],inv[405],choose[405][405],pow2[405]; 229 230 void precompute(){ 231 fact[0]=1; 232 inv[0]=1; 233 for (int i=1;i<=N;i++){ 234 fact[i]=(fact[i-1]*i)%MOD; 235 inv[i]=fastexp(fact[i],MOD-2); 236 } 237 for (int i=0;i<=N;i++) 238 for (int j=0;j<=i;j++) 239 choose[i][j]=((fact[i]*inv[j])%MOD*inv[i-j])%MOD; 240 for (int i=0;i<=N;i++) 241 pow2[i]=fastexp(2,i); 242 } 243 244 int main() 245 { 246 cin>>N>>MOD; 247 precompute(); 248 dp[0][0]=1; 249 for (int i=0;i<N;i++){ 250 for (int j=0;j<=i;j++){ 251 for (int k=1;i+k<=N;k++){ 252 dp[i+k+1][j+k]+=((dp[i][j]*pow2[k-1])%MOD*choose[j+k][k]); 253 dp[i+k+1][j+k]%=MOD; 254 } 255 } 256 } 257 ll ans=0; 258 for (int i=0;i<=N;i++) 259 ans=(ans+dp[N+1][i])%MOD; 260 cout<<ans<<endl; 261 return 0; 262 } 263 ``` 264 265 [1515F - Phoenix and Earthquake](/contest/1515/problem/F "Codeforces Global Round 14") 266 267 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 268 269 **Tutorial** 270 271 Tutorial is loading... 272 273 **Solution** 274 275 ``` 276 // Fix a spanning tree 277 // Pick a leaf, either merge it into its parent or postpone it to the end 278 #include <cstdio> 279 #include <vector> 280 #include <algorithm> 281 282 const int MAXV=300005; 283 const int MAXE=300005; 284 285 int N,M,X; 286 long long as[MAXV]; 287 288 int elist[MAXE*2]; 289 int head[MAXV]; 290 int prev[MAXE*2]; 291 int tot=0; 292 293 bool vis[MAXV]; 294 295 int ans[MAXV]; 296 int front,back; 297 298 void dfs(int u){ 299 vis[u]=true; 300 for(int e=head[u];e!=-1;e=prev[e]){ 301 int v=elist[e^1]; 302 if(vis[v]) continue; 303 dfs(v); 304 if(as[u]+as[v]>=X){ 305 as[u]+=as[v]-X; 306 ans[front++]=e>>1; 307 }else{ 308 ans[--back]=e>>1; 309 } 310 } 311 } 312 313 int main(){ 314 scanf("%d %d %d",&N,&M,&X); 315 long long total=0; 316 for(int i=0;i<N;i++){ 317 scanf("%lld",&as[i]); 318 total+=as[i]; 319 } 320 if(total<1LL*(N-1)*X){ 321 printf("NO\n"); 322 return 0; 323 } 324 std::fill(head,head+N,-1); 325 for(int i=0;i<M*2;i++){ 326 int U; 327 scanf("%d",&U); 328 U--; 329 prev[i]=head[U]; 330 head[U]=i; 331 elist[i]=U; 332 } 333 back=N-1; 334 dfs(0); 335 printf("YES\n"); 336 for(int i=0;i<N-1;i++){ 337 printf("%d\n",ans[i]+1); 338 } 339 } 340 ``` 341 342 [1515G - Phoenix and Odometers](/contest/1515/problem/G "Codeforces Global Round 14") 343 344 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 345 346 **Tutorial** 347 348 Tutorial is loading... 349 350 **Solution** 351 352 ``` 353 #include <cstdio> 354 #include <vector> 355 #include <cassert> 356 #include <algorithm> 357 #include <cmath> 358 359 using ll = long long; 360 361 std::vector<std::pair<int,int> > fwd[200005]; 362 std::vector<std::pair<int,int> > rev[200005]; 363 364 int vis[200005]; 365 int cc[200005]; 366 ll offset[200005]; 367 int ncc; 368 ll loop[200005]; 369 std::vector<int> ord; 370 371 ll gcd(ll a,ll b){ 372 return b?gcd(b,a%b):a; 373 } 374 375 void dfs_fwd(int x){ 376 vis[x]=1; 377 for(auto e:fwd[x]){ 378 int y=e.first; 379 if(vis[y]!=1){ 380 dfs_fwd(y); 381 } 382 } 383 ord.push_back(x); 384 } 385 386 void dfs_rev(int x){ 387 vis[x]=2; 388 for(auto e:rev[x]){ 389 int y=e.first,l=e.second; 390 if(vis[y]!=2){ 391 cc[y]=cc[x]; 392 offset[y]=offset[x]+l; 393 dfs_rev(y); 394 }else if(cc[y]==cc[x]){ 395 loop[cc[x]]=gcd(loop[cc[x]],std::llabs(offset[x]+l-offset[y])); 396 } 397 } 398 } 399 400 int main(){ 401 int N,M; 402 scanf("%d %d",&N,&M); 403 for(int i=0;i<M;i++){ 404 int A,B,L; 405 scanf("%d %d %d",&A,&B,&L); 406 A--,B--; 407 fwd[A].push_back({B,L}); 408 rev[B].push_back({A,L}); 409 } 410 for(int i=0;i<N;i++){ 411 if(vis[i]!=1){ 412 dfs_fwd(i); 413 } 414 } 415 std::reverse(ord.begin(),ord.end()); 416 for(int i:ord){ 417 if(vis[i]!=2){ 418 cc[i]=ncc++; 419 offset[i]=0; 420 dfs_rev(i); 421 } 422 } 423 int Q; 424 scanf("%d",&Q); 425 for(int i=0;i<Q;i++){ 426 int V,S,T; 427 scanf("%d %d %d",&V,&S,&T); 428 V--; 429 assert(0<=S&&S<T); 430 if(S%gcd(loop[cc[V]],T)==0){ 431 printf("YES\n"); 432 }else{ 433 printf("NO\n"); 434 } 435 } 436 } 437 ``` 438 439 [1515H - Phoenix and Bits](/contest/1515/problem/H "Codeforces Global Round 14") 440 441 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 442 443 **Tutorial** 444 445 Tutorial is loading... 446 447 **Solution** 448 449 ``` 450 #include <cstdio> 451 #include <cassert> 452 #include <utility> 453 #include <functional> 454 455 //numbers up to 2^MAXLOGX-1 456 const int MAXLOGX=20; 457 458 template<int k> 459 struct Trie{ 460 Trie<k-1>* chd[2]; 461 int cnt; 462 int lazy; 463 int has[2]; 464 int get_cnt(){ 465 assert(this!=NULL); 466 return cnt; 467 } 468 int get_has(int d){ 469 assert(this!=NULL); 470 push(); 471 assert(has[d]<(1<<(k+1))); 472 return has[d]; 473 } 474 Trie(Trie<k-1>* l,Trie<k-1>* r):chd{l,r},cnt(0),lazy(0),has{0,0}{ 475 if(l){ 476 cnt+=l->get_cnt(); 477 has[0]|=l->get_has(0)|(1<<k); 478 has[1]|=l->get_has(1); 479 } 480 if(r){ 481 cnt+=r->get_cnt(); 482 has[0]|=r->get_has(0); 483 has[1]|=r->get_has(1)|(1<<k); 484 } 485 assert(has[0]<(1<<(k+1))); 486 assert(has[1]<(1<<(k+1))); 487 } 488 void push(){ 489 assert(lazy<(1<<(k+1))); 490 if(!lazy) return; 491 //handle kth bit 492 if(lazy&(1<<k)){ 493 std::swap(chd[0],chd[1]); 494 if((has[0]^has[1])&(1<<k)){ 495 has[0]^=(1<<k); 496 has[1]^=(1<<k); 497 } 498 lazy^=(1<<k); 499 } 500 //handle rest of bits 501 int flip=(has[0]^has[1])&lazy; 502 has[0]^=flip; 503 has[1]^=flip; 504 if(chd[0]) chd[0]->lazy^=lazy; 505 if(chd[1]) chd[1]->lazy^=lazy; 506 lazy=0; 507 assert(has[0]<(1<<(k+1))); 508 assert(has[1]<(1<<(k+1))); 509 } 510 }; 511 512 template<> 513 struct Trie<-1>{ 514 int lazy; 515 Trie():lazy(0){ 516 } 517 int get_cnt(){ 518 assert(this!=NULL); 519 return 1; 520 } 521 int get_has(int d){ 522 assert(this!=NULL); 523 return 0; 524 } 525 }; 526 527 template<int k> 528 Trie<k>* create(int x){ 529 if(x&(1<<k)){ 530 return new Trie<k>(NULL,create<k-1>(x)); 531 }else{ 532 return new Trie<k>(create<k-1>(x),NULL); 533 } 534 } 535 template<> 536 Trie<-1>* create(int x){ 537 return new Trie<-1>(); 538 } 539 540 template<int k> 541 std::pair<Trie<k-1>*,Trie<k-1>*> destruct(Trie<k>* a){ 542 assert(a!=NULL); 543 a->push(); 544 auto res=std::make_pair(a->chd[0],a->chd[1]); 545 delete a; 546 return res; 547 } 548 549 template<int k> 550 Trie<k>* join(Trie<k-1>* l,Trie<k-1>* r){ 551 if(l==NULL&&r==NULL) return NULL; 552 return new Trie<k>(l,r); 553 } 554 555 template<int k> 556 Trie<k>* merge(Trie<k>* a,Trie<k>* b){ 557 if(!a) return b; 558 if(!b) return a; 559 auto aa=destruct(a); 560 auto bb=destruct(b); 561 Trie<k-1>* l=merge<k-1>(aa.first,bb.first); 562 Trie<k-1>* r=merge<k-1>(aa.second,bb.second); 563 return join<k>(l,r); 564 } 565 566 template<> 567 Trie<-1>* merge<-1>(Trie<-1>* a,Trie<-1>* b){ 568 if(!a) return b; 569 if(!b) return a; 570 delete b; 571 return a; 572 } 573 574 template<int k> 575 //<thres and >=thres 576 std::pair<Trie<k>*,Trie<k>*> split(Trie<k>* a,int thres){ 577 if(a==NULL){ 578 return {NULL,NULL}; 579 } 580 if(thres<=0) return {NULL,a}; 581 if(thres>=(1<<(k+1))) return {a,NULL}; 582 assert(k>=0); 583 auto aa=destruct(a); 584 if(thres<(1<<k)){ 585 Trie<k-1>* l,*r; 586 std::tie(l,r)=split<k-1>(aa.first,thres); 587 return std::make_pair(join<k>(l,NULL),join<k>(r,aa.second)); 588 }else if(thres>(1<<k)){ 589 Trie<k-1>* l,*r; 590 std::tie(l,r)=split<k-1>(aa.second,thres-(1<<k)); 591 return std::make_pair(join<k>(aa.first,l),join<k>(NULL,r)); 592 }else{ 593 return std::make_pair(join<k>(aa.first,NULL),join<k>(NULL,aa.second)); 594 } 595 } 596 597 template<> 598 std::pair<Trie<-1>*,Trie<-1>*> split<-1>(Trie<-1>* a,int thres){ 599 assert(0); 600 } 601 602 template<int k> 603 Trie<k>* update(Trie<k>* a,int val){ 604 if(a==NULL) return NULL; 605 a->push(); 606 assert(val<(1<<(k+1))); 607 if((val&a->has[0]&a->has[1])==0){ 608 a->lazy^=(val&a->has[0]); 609 return a; 610 } 611 Trie<k-1>* l,*r; 612 std::tie(l,r)=destruct(a); 613 l=update<k-1>(l,val&~(1<<k)); 614 r=update<k-1>(r,val&~(1<<k)); 615 if(val&(1<<k)){ 616 return join<k>(NULL,merge<k-1>(l,r)); 617 }else{ 618 return join<k>(l,r); 619 } 620 } 621 622 template<> 623 Trie<-1>* update<-1>(Trie<-1>* a,int val){ 624 return a; 625 } 626 627 int main(){ 628 Trie<MAXLOGX-1>* root=NULL; 629 int N,Q; 630 scanf("%d %d",&N,&Q); 631 for(int i=0;i<N;i++){ 632 int A; 633 scanf("%d",&A); 634 root=merge(root,create<MAXLOGX-1>(A)); 635 } 636 for(int i=0;i<Q;i++){ 637 int T,L,R; 638 scanf("%d %d %d",&T,&L,&R); 639 Trie<MAXLOGX-1>* left,*right; 640 std::tie(left,root)=split(root,L); 641 std::tie(root,right)=split(root,R+1); 642 if(T==4){ 643 printf("%d\n",root?root->cnt:0); 644 }else{ 645 int X; 646 scanf("%d",&X); 647 if(root!=NULL){ 648 if(T==1){ 649 root->lazy^=((1<<MAXLOGX)-1); 650 root=update(root,X^((1<<MAXLOGX)-1)); 651 root->lazy^=((1<<MAXLOGX)-1); 652 }else if(T==2){ 653 root=update(root,X); 654 }else if(T==3){ 655 assert(X<(1<<MAXLOGX)); 656 root->lazy^=X; 657 } 658 } 659 } 660 root=merge(root,left); 661 root=merge(root,right); 662 } 663 } 664 ``` 665 666 [1515I - Phoenix and Diamonds](/contest/1515/problem/I "Codeforces Global Round 14") 667 668 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 669 670 **Tutorial** 671 672 Tutorial is loading... 673 674 **Solution** 675 676 ``` 677 #include <cstdio> 678 #include <algorithm> 679 #include <functional> 680 #include <utility> 681 #include <numeric> 682 #include <cassert> 683 684 using ll=long long; 685 686 const ll INF=1e18+7; 687 688 struct Diamond{ 689 int w,v,t; 690 ll a; 691 }diamonds[200005]; 692 int index[200005]; 693 int N; 694 695 struct Node{ 696 ll sum_w[31];//sum of weights of all diamonds with weight <2^k 697 ll sum_v[31];//sum of values of all diamonds with weight <2^k 698 ll one_w[31];//sum of weights of light+first heavy when restricted to <2^k 699 ll one_v[31];//sum of values of light+first heavy when restricted to <2^k 700 }st[800005]; 701 702 void rebuild(int w,int L,int R,int a,int b){ 703 if(a>=R||b<=L) return; 704 if(R-L==1){ 705 for(int k=1;k<=30;k++){ 706 st[w].sum_w[k]=diamonds[L].a*diamonds[L].w*(diamonds[L].w<(1<<k)); 707 st[w].sum_v[k]=diamonds[L].a*diamonds[L].v*(diamonds[L].w<(1<<k)); 708 st[w].one_w[k]=INF;//query capacity never exceed INF 709 st[w].one_v[k]=INF; 710 if(diamonds[L].w>=(1<<(k-1))&&diamonds[L].w<(1<<k)&&diamonds[L].a>0){ 711 st[w].one_w[k]=diamonds[L].w; 712 st[w].one_v[k]=diamonds[L].v; 713 } 714 } 715 }else{ 716 int M=(L+R)/2; 717 rebuild(w*2+1,L,M,a,b); 718 rebuild(w*2+2,M,R,a,b); 719 for(int k=1;k<=30;k++){ 720 st[w].sum_w[k]=st[w*2+1].sum_w[k]+st[w*2+2].sum_w[k]; 721 st[w].sum_v[k]=st[w*2+1].sum_v[k]+st[w*2+2].sum_v[k]; 722 if(st[w*2+1].one_w[k]<st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]){ 723 st[w].one_w[k]=st[w*2+1].one_w[k]; 724 st[w].one_v[k]=st[w*2+1].one_v[k]; 725 }else{ 726 st[w].one_w[k]=st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]; 727 st[w].one_v[k]=st[w*2+1].sum_v[k-1]+st[w*2+2].one_v[k]; 728 } 729 } 730 } 731 } 732 733 //only consider weights <2^k 734 //take maximal prefix possible 735 void query_all(int w,int L,int R,int& i,int k,ll& cap,ll& value){ 736 assert(i>=L&&i<=R); 737 assert(R-L>0); 738 if(i==R) return; 739 if(i==L&&st[w].sum_w[k]<=cap){ 740 cap-=st[w].sum_w[k]; 741 value+=st[w].sum_v[k]; 742 i=R; 743 }else if(R-L>1){ 744 int M=(L+R)/2; 745 if(i<M){ 746 query_all(w*2+1,L,M,i,k,cap,value); 747 } 748 if(i>=M){ 749 query_all(w*2+2,M,R,i,k,cap,value); 750 } 751 } 752 } 753 754 std::array<ll,2> query_one_range_simpl(int w,int L,int R,int a,int b,int k){ 755 if(a>=R||b<=L) return {INF,0}; 756 if(a<=L&&b>=R){ 757 return {st[w].one_w[k],st[w].sum_w[k-1]}; 758 }else{ 759 int M=(L+R)/2; 760 std::array<ll,2> lsum,rsum; 761 lsum=query_one_range_simpl(w*2+1,L,M,a,b,k); 762 rsum=query_one_range_simpl(w*2+2,M,R,a,b,k); 763 if(lsum[0]<lsum[1]+rsum[0]){ 764 return {lsum[0],lsum[1]+rsum[1]}; 765 }else{ 766 return {lsum[1]+rsum[0],lsum[1]+rsum[1]}; 767 } 768 } 769 } 770 771 std::array<ll,4> query_one_range(int w,int L,int R,int a,int b,int k){ 772 if(a>=R||b<=L) return {INF,INF,0,0}; 773 if(a<=L&&b>=R){ 774 return {st[w].one_w[k],st[w].one_v[k],st[w].sum_w[k-1],st[w].sum_v[k-1]}; 775 }else{ 776 int M=(L+R)/2; 777 std::array<ll,4> lsum,rsum; 778 lsum=query_one_range(w*2+1,L,M,a,b,k); 779 rsum=query_one_range(w*2+2,M,R,a,b,k); 780 if(lsum[0]<lsum[2]+rsum[0]){ 781 return {lsum[0],lsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]}; 782 }else{ 783 return {lsum[2]+rsum[0],lsum[3]+rsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]}; 784 } 785 } 786 } 787 788 //returns min j such that one_w[i..j) <= cap, or -1 if none exist 789 //reduce cap by weight of light in [max(i,L),R) 790 int query_one_range_search_(int w,int L,int R,int& i,int k,ll& cap){ 791 assert(i>=L&&i<=R); 792 assert(R-L>0); 793 if(i==R) return -1; 794 if(i==L&&st[w].one_w[k]>cap){ 795 cap-=st[w].sum_w[k-1]; 796 i=R; 797 return -1; 798 }else if(R-L==1){ 799 assert(i==L); 800 assert(st[w].one_w[k]<=cap); 801 cap-=st[w].sum_w[k-1]; 802 i=R; 803 return R; 804 }else{ 805 int M=(L+R)/2; 806 int res=-1; 807 if(i<M){ 808 res=query_one_range_search_(w*2+1,L,M,i,k,cap); 809 } 810 if(res!=-1) return res; 811 if(i>=M){ 812 res=query_one_range_search_(w*2+2,M,R,i,k,cap); 813 } 814 return res; 815 } 816 } 817 818 int query_one_range_search(int i,int k,ll cap){ 819 //note this copy of cap will be modified 820 return query_one_range_search_(0,0,N,i,k,cap); 821 } 822 823 void query_one(int& L,int k,ll& cap,ll& value){ 824 int high=query_one_range_search(L,k,cap); 825 //v[high]<=cap 826 if(high!=-1){ 827 auto v=query_one_range(0,0,N,L,high,k); 828 L=high; 829 cap-=v[0]; 830 value+=v[1]; 831 } 832 } 833 834 ll query(ll cap){ 835 ll value=0; 836 int i=0; 837 for(int k=30;k>0;k--){ 838 query_all(0,0,N,i,k,cap,value); 839 if(i==N) break; 840 ll take=std::min(diamonds[i].a,cap/diamonds[i].w); 841 cap-=take*diamonds[i].w; 842 value+=take*diamonds[i].v; 843 i++; 844 query_one(i,k,cap,value); 845 } 846 return value; 847 } 848 849 int main(){ 850 int Q; 851 scanf("%d %d",&N,&Q); 852 for(int i=0;i<N;i++){ 853 scanf("%lld %d %d",&diamonds[i].a,&diamonds[i].w,&diamonds[i].v); 854 diamonds[i].t=i; 855 } 856 std::sort(diamonds,diamonds+N,[](Diamond x,Diamond y){ 857 return (x.v!=y.v)?(x.v>y.v):(x.w<y.w); 858 }); 859 for(int i=0;i<N;i++){ 860 index[diamonds[i].t]=i; 861 } 862 rebuild(0,0,N,0,N); 863 for(int i=0;i<Q;i++){ 864 int T; 865 scanf("%d",&T); 866 if(T==1){ 867 int K,D; 868 scanf("%d %d",&K,&D); 869 D--; 870 diamonds[index[D]].a+=K; 871 rebuild(0,0,N,index[D],index[D]+1); 872 }else if(T==2){ 873 int K,D; 874 scanf("%d %d",&K,&D); 875 D--; 876 diamonds[index[D]].a-=K; 877 assert(diamonds[index[D]].a>=0); 878 rebuild(0,0,N,index[D],index[D]+1); 879 }else{ 880 ll C; 881 scanf("%lld",&C); 882 printf("%lld\n",query(C)); 883 } 884 } 885 } 886 ```