#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; struct client { int start, offset, count, value; client(int a,int b,int c, int d): start(a), offset(b), count(c), value(d) { } }; int n,m; list<client> L; vector<pair<int,int> > vv; vector<long long> vvv; vector<long long> w; void print() { for(const auto& x : L) { cout << x.start << " " << x.offset << " " << x.count << " " << x.value << endl; } cout <<endl; } int main() { ios_base::sync_with_stdio(false); int x,value,res; list<client>::iterator it; list<client>::iterator nextIt; list<client>::iterator prevIt; cin >>n>>m; client prev(0,0,1,0); for(int i=0;i<n;i++) { cin >>x; if(L.size()>0 && L.back().start==x) { L.back().count++; } else { prev.offset=x-prev.start; prev.start=x; } L.push_back(prev); } for(int i=0;i<m;i++) { cin >>x; vv.push_back(make_pair(x,i)); vvv.push_back(0); w.push_back(0); } sort(vv.begin(),vv.end()); for(int i=0;i<m;i++) { value=vv[i].first; if(i>0) value-=vv[i-1].first; res=0; it = L.begin(); while(it!=L.end()) { if(it->offset < value) { x = value - it->offset; it->start += x; it->value +=it->count*x; it->value +=value*((it->count*(it->count-1))/2); cout <<it->count*x<<endl; cout << value*((it->count*(it->count-1))/2)<<endl; it->offset = 0; nextIt=it; nextIt++; res+=it->value; if(nextIt!=L.end()) { nextIt->offset -= x + value*(it->count-1); } if(it != L.begin()) { prevIt->count+=it->count; prevIt->value += it->value; L.erase(it); it=prevIt; } } else { it->offset-=value; x=value*((it->count*(it->count-1))/2); it->value+=x; res+=it->value; nextIt=it; nextIt++; if(nextIt!=L.end()) { nextIt->offset -= x; } } prevIt=it; it++; } w[i]=res; } for(int i=0;i<m;i++) { vvv[vv[i].second]=w[i]; } for(int i=0;i<m;i++) { cout <<vvv[i]<<endl; } }
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 | #include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; struct client { int start, offset, count, value; client(int a,int b,int c, int d): start(a), offset(b), count(c), value(d) { } }; int n,m; list<client> L; vector<pair<int,int> > vv; vector<long long> vvv; vector<long long> w; void print() { for(const auto& x : L) { cout << x.start << " " << x.offset << " " << x.count << " " << x.value << endl; } cout <<endl; } int main() { ios_base::sync_with_stdio(false); int x,value,res; list<client>::iterator it; list<client>::iterator nextIt; list<client>::iterator prevIt; cin >>n>>m; client prev(0,0,1,0); for(int i=0;i<n;i++) { cin >>x; if(L.size()>0 && L.back().start==x) { L.back().count++; } else { prev.offset=x-prev.start; prev.start=x; } L.push_back(prev); } for(int i=0;i<m;i++) { cin >>x; vv.push_back(make_pair(x,i)); vvv.push_back(0); w.push_back(0); } sort(vv.begin(),vv.end()); for(int i=0;i<m;i++) { value=vv[i].first; if(i>0) value-=vv[i-1].first; res=0; it = L.begin(); while(it!=L.end()) { if(it->offset < value) { x = value - it->offset; it->start += x; it->value +=it->count*x; it->value +=value*((it->count*(it->count-1))/2); cout <<it->count*x<<endl; cout << value*((it->count*(it->count-1))/2)<<endl; it->offset = 0; nextIt=it; nextIt++; res+=it->value; if(nextIt!=L.end()) { nextIt->offset -= x + value*(it->count-1); } if(it != L.begin()) { prevIt->count+=it->count; prevIt->value += it->value; L.erase(it); it=prevIt; } } else { it->offset-=value; x=value*((it->count*(it->count-1))/2); it->value+=x; res+=it->value; nextIt=it; nextIt++; if(nextIt!=L.end()) { nextIt->offset -= x; } } prevIt=it; it++; } w[i]=res; } for(int i=0;i<m;i++) { vvv[vv[i].second]=w[i]; } for(int i=0;i<m;i++) { cout <<vvv[i]<<endl; } } |