Phoenix and Diamonds solution codeforces – Phoenix wonders what it is like to rob diamonds from a jewelry store! 2021

Phoenix and Diamonds solution codeforces

Phoenix and Diamonds solution codeforces Phoenix and Diamonds solution codeforces Phoenix and Diamonds solution codeforces

Phoenix wonders what it is like to rob diamonds from a jewelry store!

There are nn types of diamonds. The ii-th type has weight wiwi and value vivi. The store initially has aiai diamonds of the ii-th type.

Each day, for qq days, one of the following will happen:

  1. A new shipment of kiki diamonds of type didi arrive.
  2. The store sells kiki diamonds of type didi.
  3. Phoenix wonders what will happen if he robs the store using a bag that can fit diamonds with total weight not exceeding cici. If he greedily takes diamonds of the largest value that fit, how much value would be taken? If there are multiple diamonds with the largest value, he will take the one with minimum weight. If, of the diamonds with the largest value, there are multiple with the same minimum weight, he will take any of them.

Of course, since Phoenix is a law-abiding citizen, this is all a thought experiment and he never actually robs any diamonds from the store. This means that queries of type 33 do not affect the diamonds in the store.

Input Phoenix and Diamonds solution codeforces

The first line contains two integers nn and qq (1n21051≤n≤2⋅1051q1051≤q≤105) — the number of types of diamonds and number of days, respectively.

The next nn lines describe each type of diamond. The ii-th line will contain three integers aiaiwiwi, and vivi (0ai1050≤ai≤1051wi,vi1051≤wi,vi≤105) — the initial number of diamonds of the ii-th type, the weight of diamonds of the ii-th type, and the value of diamonds of the ii-th type, respectively.

The next qq lines contain the queries. For each query, the first integer of each line is tt (1t31≤t≤3) — the type of query.

If t=1t=1, then two integers kikididi follow (1ki1051≤ki≤1051din1≤di≤n). This means that a new shipment of kiki diamonds arrived, each of type didi.

If t=2t=2, then two integers kikididi follow (1ki1051≤ki≤1051din1≤di≤n). This means that the store has sold kiki diamonds, each of type didi. It is guaranteed that the store had the diamonds before they sold them.

If t=3t=3, an integer cici will follow (1ci10181≤ci≤1018) — the weight capacity of Phoenix’s bag.

It is guaranteed that there is at least one query where t=3t=3.

Output Phoenix and Diamonds solution codeforces

Print the answer for each query of the third type (t=3t=3).

Example Phoenix and Diamonds solution codeforces

input Phoenix and Diamonds solution codeforces

Copy
3 5
2 3 4
1 5 1
0 2 4
3 6
1 3 3
3 10
2 2 3
3 30

output

Copy
8
16
13
Note Phoenix and Diamonds solution codeforces

For the first query where t=3t=3, Phoenix can fit 22 diamonds of type 11, with total weight 66 and value 88.

For the second query where t=3t=3, Phoenix will first fit in 33 diamonds of type 33, then one diamond of type 11 for a total weight of 99 and a value of 1616. Note that diamonds of type 33 are prioritized over type 11 because type 33 has equal value but less weight.

For the final query where t=3t=3, Phoenix can fit every diamond for a total value of 1313.

GNU C++ (64)

#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)
using namespace std;
typedef long long LL;
const LL INFLL=0X3F3F3F3F3F3F3F3FLL;
const int N=200005;
int n,Q,_w[N],_v[N],id[N],_id[N];
LL _a[N],sw0[N*4][18],sv0[N*4][18],sw1[N*4][18];
void bud(int k1,int k2,int k3,int k4,int k5){
if(k2>k5||k3<k4)return;
if(k2==k3){
rep(k,1,17){
if(_w[id[k2]]<(1<<k)){
sw0[k1][k]=_a[id[k2]]*_w[id[k2]];
sv0[k1][k]=_a[id[k2]]*_v[id[k2]];
}
sw1[k1][k]=INFLL;
if(_w[id[k2]]>=(1<<(k-1))&&_w[id[k2]]<(1<<k)&&_a[id[k2]]){
sw1[k1][k]=_w[id[k2]];
}
}
return;
}
int mid=(k2+k3)>>1;
bud(k1*2,k2,mid,k4,k5),bud(k1*2+1,mid+1,k3,k4,k5);
rep(k,1,17){
sw0[k1][k]=sw0[k1*2][k]+sw0[k1*2+1][k];
sv0[k1][k]=sv0[k1*2][k]+sv0[k1*2+1][k];
if(sw1[k1*2][k]<sw0[k1*2][k-1]+sw1[k1*2+1][k]){
sw1[k1][k]=sw1[k1*2][k];
}else{
sw1[k1][k]=sw0[k1*2][k-1]+sw1[k1*2+1][k];
}
}
}
void add(int x,int y){
_a[x]+=y;
bud(1,1,n,_id[x],_id[x]);
}
LL rem,vv; int _k;
void clip(){
while(_k>0&&(1<<(_k-1))>rem)--_k;
}
void qry(int k1,int k2,int k3){
if(k2==k3){
LL tt=min(_a[id[k2]],rem/_w[id[k2]]);
rem-=tt*_w[id[k2]];
vv+=tt*_v[id[k2]];
return;
}
int mid=(k2+k3)>>1;
clip();
if(sw0[k1][_k]<=rem){
rem-=sw0[k1][_k];
vv+=sv0[k1][_k];
return;
}
if(sw1[k1][_k]>rem&&sw0[k1][_k-1]<=rem){
rem-=sw0[k1][_k-1];
vv+=sv0[k1][_k-1];
return;
}
qry(k1*2,k2,mid);
clip();
qry(k1*2+1,mid+1,k3);
}
void sol(LL x){
_k=17,rem=x,vv=0;
clip();
qry(1,1,n);
printf("%lld\n",vv);
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
scanf("%d%d",&n,&Q);
rep(i,1,n){
scanf("%lld%d%d",&_a[i],&_w[i],&_v[i]);
id[i]=i;
}
sort(id+1,id+1+n,[&](int x,int y){return _v[x]^_v[y]?_v[x]>_v[y]:_w[x]<_w[y];});
rep(i,1,n)_id[id[i]]=i;
bud(1,1,n,1,n);
while(Q--){
int t;
scanf("%d",&t);
if(t==1){
int x,y;
scanf("%d%d",&x,&y);
add(y,x);
}else if(t==2){
int x,y;
scanf("%d%d",&x,&y);
add(y,-x);
}else{
LL x;
scanf("%lld",&x);
sol(x);
}
}
return 0;
}

GNU C11

#include <stdio.h>
#include <sys/time.h>

#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
#define LG 18 /* LG = floor(log2(10^5)) + 1 */
#define INF 0x3f3f3f3f3f3f3f3f

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int X;

void srand_() {
struct timeval tv;

gettimeofday(&tv, NULL);
X = tv.tv_sec ^ tv.tv_usec;
if (X % 2 == 0)
X++;
}

int rand_() {
return (X *= 3) >> 1;
}

long long aa[N]; int vv[N], ww[N], ii[N], inv[N], n;

void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

while (j < k) {
int c = vv[ii[j]] != vv[i_] ? vv[i_] - vv[ii[j]] : ww[ii[j]] - ww[i_];

if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}

long long vsm[LG + 1][N_ * 2], wsm[LG + 1][N_ * 2], wsm_[LG + 1][N_ * 2]; int n_;

void pul(int lg, int i) {
int l = i << 1, r = l | 1;

vsm[lg][i] = vsm[lg][l] + vsm[lg][r], wsm[lg][i] = wsm[lg][l] + wsm[lg][r];
wsm_[lg][i] = min(wsm_[lg][l], wsm[lg][l] + wsm_[lg][r]);
}

void build() {
int lg, i;

n_ = 1;
while (n_ < n)
n_ <<= 1;
for (lg = 0; lg <= LG; lg++) {
for (i = 0; i < n_; i++) {
long long a = aa[ii[i]];
int v = vv[ii[i]], w = ww[ii[i]];

if (i >= n)
vsm[lg][n_ + i] = 0, wsm[lg][n_ + i] = 0, wsm_[lg][n_ + i] = INF;
else if (w < (1 << lg))
vsm[lg][n_ + i] = a * v, wsm[lg][n_ + i] = a * w, wsm_[lg][n_ + i] = INF;
else
vsm[lg][n_ + i] = 0, wsm[lg][n_ + i] = 0, wsm_[lg][n_ + i] = a == 0 ? INF : w;
}
for (i = n_ - 1; i > 0; i--)
pul(lg, i);
}
}

void update(int lg, int i) {
long long a = aa[ii[i]];
int v = vv[ii[i]], w = ww[ii[i]];

if (w < (1 << lg))
vsm[lg][n_ + i] = a * v, wsm[lg][n_ + i] = a * w, wsm_[lg][n_ + i] = INF;
else
vsm[lg][n_ + i] = 0, wsm[lg][n_ + i] = 0, wsm_[lg][n_ + i] = a == 0 ? INF : w;
i += n_;
while (i > 1)
pul(lg, i >>= 1);
}

void update_(int i, int a) {
int lg;

aa[ii[i]] += a;
for (lg = 0; lg <= LG; lg++)
update(lg, i);
}

long long c, ans;

int jump(int lg, int i) {
int l = i, r = n_ - 1;

for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((l & 1) == 1) {
if (c >= wsm_[lg][l]) {
while (l < n_)
if (c >= wsm_[lg][l << 1 | 0])
l = l << 1 | 0;
else
c -= wsm[lg][l << 1 | 0], ans += vsm[lg][l << 1 | 0], l = l << 1 | 1;
l -= n_;
c -= ww[ii[l]], ans += vv[ii[l]];
return l + 1;
} else if (c >= wsm[lg][l])
c -= wsm[lg][l], ans += vsm[lg][l], l++;
else {
while (l < n_)
if (c < wsm[lg][l << 1 | 0])
l = l << 1 | 0;
else
c -= wsm[lg][l << 1 | 0], ans += vsm[lg][l << 1 | 0], l = l << 1 | 1;
l -= n_;
ans += c / ww[ii[l]] * vv[ii[l]], c %= ww[ii[l]];
return l + 1;
}
}
return n_;
}

int main() {
int q, i;

srand_();
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++) {
scanf("%lld%d%d", &aa[i], &ww[i], &vv[i]);
ii[i] = i;
}
sort(ii, 0, n);
for (i = 0; i < n; i++)
inv[ii[i]] = i;
build();
while (q--) {
int t;

scanf("%d", &t);
if (t == 1 || t == 2) {
int a;

scanf("%d%d", &a, &i), i--;
update_(inv[i], t == 1 ? a : -a);
} else {
int lg, i;

scanf("%lld", &c);
ans = 0;
for (lg = LG, i = 0; lg >= 0 && i < n_; lg--)
i = jump(lg, i);
printf("%lld\n", ans);
}
}
return 0;
}


Phoenix and Diamonds solution codeforces Phoenix and Diamonds solution codeforces Phoenix and Diamonds solution codeforces
Phoenix and Diamonds solution codeforces Splitting a String Into Descending Consecutive Values Minimum Adjacent Swaps to Reach the Kth Smallest Number Minimum Interval to Include Each Query
 
 

Leave a Comment