#include <cstdio> #include <vector> #include <algorithm> int main() { int clients,ovens; std::vector<long long int> time(210000,0); std::vector<long long int> timesum(210000,0); std::vector<std::pair<long long int, int> > speedm(210000,std::make_pair(0,0)); std::vector<long long int> speeds(210000,0); scanf("%d %d",&clients,&ovens); for (int i=0; i<clients; ++i) { scanf("%lld",&time[i]); timesum[i] = time[i] + ((i-1>=0)?timesum[i-1]:0); } for (int i=0; i<ovens; ++i) { scanf("%lld",&speedm[i].first); speedm[i].second = i; } std::sort(speedm.begin(), speedm.begin()+ovens); for (int i=0; i<ovens; ++i) { speeds[i]=speedm[i].first; } //for each client check which ovens are perfect for him std::vector<std::pair<int,int> > order; std::vector<std::pair<int,int> > blocks(210000, std::make_pair(ovens+1,-1)); //last good client for oven int blocks_cnt = 0; for (int i=0; i<clients; ++i) { long long int delta=time[i]-((i-1>=0)?time[i-1]:0); if (blocks_cnt==0 || (speeds[blocks[blocks_cnt-1].first]>delta && blocks[blocks_cnt-1].first>0)) { //add block int l=0; int ro,r; ro=r=((blocks_cnt==0)?(ovens):(blocks[blocks_cnt-1].first)); while (l<r) { int m=(l+r)/2; if (speeds[m]<=delta) { l=m+1; } else { r=m; } } if (l<ro) { blocks[blocks_cnt++]=(std::make_pair(l,i-1)); //printf("BLOCK %d %d\n",i,l); } } else { //del block bool deleted = false; while (blocks_cnt>0) { int on = blocks[blocks_cnt-1].first; int lg = blocks[blocks_cnt-1].second; long long int rtime = time[i]-((lg>=0)?time[lg]:0); if (rtime>=speeds[on]*(i-lg)) { //printf("DELETE BLOCK %d\n",i); blocks_cnt--; deleted = true; } else { break; } } //add new block if (deleted) { int lg = blocks[blocks_cnt].second; int l = blocks[blocks_cnt].first+1; int ro,r; ro = r = ((blocks_cnt>0)?(blocks[blocks_cnt-1].first):(ovens)); while (l<r) { int m = (l+r)/2; long long int rtime = time[i]-((lg>=0)?time[lg]:0); if (rtime>=speeds[m]*(i-lg)) { l=m+1; } else { r=m; } } if (l<ro) { blocks[blocks_cnt++]=(std::make_pair(l,lg)); //printf("BLOCK2 %d %d\n",lg,l); } } } if (blocks_cnt>0) { order.push_back(std::make_pair(blocks[blocks_cnt-1].first,i)); //printf("ORDER oven=%d bad for client=%d\n",blocks[blocks_cnt-1].first,i); } } std::sort(order.begin(),order.end()); int pos = 0; long long int current_val_a = 0, current_val_b = 0;; std::vector<int> begins(210000,-1); std::vector<int> ends(210000,-1); std::vector<long long int> result(210000,0); //for each oven add bad clients for (int i=0; i<ovens; ++i) { while (pos<order.size() && order[pos].first == i) { int cli = order[pos].second; long long int begin,end; //printf("ADDING %d %d\n",i,cli); pos++; begin = end = cli; if (cli>0 && begins[cli-1]>=0) { long long int tmpb = begins[cli-1]; long long int tmpe = cli-1; current_val_a -= (tmpe-tmpb+2)*(tmpe-tmpb+1)/2; current_val_b -= timesum[tmpe]-((tmpb-1>=0)?timesum[tmpb-1]:0)-((tmpb-1>=0)?((tmpe-tmpb+1)*time[tmpb-1]):0); begin = begins[cli-1]; } if (ends[cli+1]>=0) { long long int tmpb = cli+1; long long int tmpe = ends[cli+1]; current_val_a -= (tmpe-tmpb+2)*(tmpe-tmpb+1)/2; current_val_b -= timesum[tmpe]-((tmpb-1>=0)?timesum[tmpb-1]:0)-((tmpb-1>=0)?((tmpe-tmpb+1)*time[tmpb-1]):0); end = ends[cli+1]; } current_val_a += (end-begin+2)*(end-begin+1)/2; current_val_b += timesum[end]-((begin-1>=0)?timesum[begin-1]:0)-((begin-1>=0)?((end-begin+1)*time[begin-1]):0); ends[begin] = end; begins[end] = begin; } result[speedm[i].second] = current_val_a*speeds[i]-current_val_b; //printf("%lld %lld\n",current_val_a,current_val_b); //printf("VAL %lld\n",current_val_a*speeds[i]-current_val_b); } for (int i=0; i<ovens; ++i) { printf("%lld\n",result[i]); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include <cstdio> #include <vector> #include <algorithm> int main() { int clients,ovens; std::vector<long long int> time(210000,0); std::vector<long long int> timesum(210000,0); std::vector<std::pair<long long int, int> > speedm(210000,std::make_pair(0,0)); std::vector<long long int> speeds(210000,0); scanf("%d %d",&clients,&ovens); for (int i=0; i<clients; ++i) { scanf("%lld",&time[i]); timesum[i] = time[i] + ((i-1>=0)?timesum[i-1]:0); } for (int i=0; i<ovens; ++i) { scanf("%lld",&speedm[i].first); speedm[i].second = i; } std::sort(speedm.begin(), speedm.begin()+ovens); for (int i=0; i<ovens; ++i) { speeds[i]=speedm[i].first; } //for each client check which ovens are perfect for him std::vector<std::pair<int,int> > order; std::vector<std::pair<int,int> > blocks(210000, std::make_pair(ovens+1,-1)); //last good client for oven int blocks_cnt = 0; for (int i=0; i<clients; ++i) { long long int delta=time[i]-((i-1>=0)?time[i-1]:0); if (blocks_cnt==0 || (speeds[blocks[blocks_cnt-1].first]>delta && blocks[blocks_cnt-1].first>0)) { //add block int l=0; int ro,r; ro=r=((blocks_cnt==0)?(ovens):(blocks[blocks_cnt-1].first)); while (l<r) { int m=(l+r)/2; if (speeds[m]<=delta) { l=m+1; } else { r=m; } } if (l<ro) { blocks[blocks_cnt++]=(std::make_pair(l,i-1)); //printf("BLOCK %d %d\n",i,l); } } else { //del block bool deleted = false; while (blocks_cnt>0) { int on = blocks[blocks_cnt-1].first; int lg = blocks[blocks_cnt-1].second; long long int rtime = time[i]-((lg>=0)?time[lg]:0); if (rtime>=speeds[on]*(i-lg)) { //printf("DELETE BLOCK %d\n",i); blocks_cnt--; deleted = true; } else { break; } } //add new block if (deleted) { int lg = blocks[blocks_cnt].second; int l = blocks[blocks_cnt].first+1; int ro,r; ro = r = ((blocks_cnt>0)?(blocks[blocks_cnt-1].first):(ovens)); while (l<r) { int m = (l+r)/2; long long int rtime = time[i]-((lg>=0)?time[lg]:0); if (rtime>=speeds[m]*(i-lg)) { l=m+1; } else { r=m; } } if (l<ro) { blocks[blocks_cnt++]=(std::make_pair(l,lg)); //printf("BLOCK2 %d %d\n",lg,l); } } } if (blocks_cnt>0) { order.push_back(std::make_pair(blocks[blocks_cnt-1].first,i)); //printf("ORDER oven=%d bad for client=%d\n",blocks[blocks_cnt-1].first,i); } } std::sort(order.begin(),order.end()); int pos = 0; long long int current_val_a = 0, current_val_b = 0;; std::vector<int> begins(210000,-1); std::vector<int> ends(210000,-1); std::vector<long long int> result(210000,0); //for each oven add bad clients for (int i=0; i<ovens; ++i) { while (pos<order.size() && order[pos].first == i) { int cli = order[pos].second; long long int begin,end; //printf("ADDING %d %d\n",i,cli); pos++; begin = end = cli; if (cli>0 && begins[cli-1]>=0) { long long int tmpb = begins[cli-1]; long long int tmpe = cli-1; current_val_a -= (tmpe-tmpb+2)*(tmpe-tmpb+1)/2; current_val_b -= timesum[tmpe]-((tmpb-1>=0)?timesum[tmpb-1]:0)-((tmpb-1>=0)?((tmpe-tmpb+1)*time[tmpb-1]):0); begin = begins[cli-1]; } if (ends[cli+1]>=0) { long long int tmpb = cli+1; long long int tmpe = ends[cli+1]; current_val_a -= (tmpe-tmpb+2)*(tmpe-tmpb+1)/2; current_val_b -= timesum[tmpe]-((tmpb-1>=0)?timesum[tmpb-1]:0)-((tmpb-1>=0)?((tmpe-tmpb+1)*time[tmpb-1]):0); end = ends[cli+1]; } current_val_a += (end-begin+2)*(end-begin+1)/2; current_val_b += timesum[end]-((begin-1>=0)?timesum[begin-1]:0)-((begin-1>=0)?((end-begin+1)*time[begin-1]):0); ends[begin] = end; begins[end] = begin; } result[speedm[i].second] = current_val_a*speeds[i]-current_val_b; //printf("%lld %lld\n",current_val_a,current_val_b); //printf("VAL %lld\n",current_val_a*speeds[i]-current_val_b); } for (int i=0; i<ovens; ++i) { printf("%lld\n",result[i]); } return 0; } |