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 `#include #define endl '\n' using namespace std; const int M = 200010; set< pair< long long, int > > secik; set< pair< long long, int > >::iterator it; long long n, m, par[M], i[M], sum[M], pocz[M], nex[M], need[M], x; long long Sum, Sum2, Ile, len, id, ans[M], inf = 1e18; vector< pair< long long, int > > tab; long long d ( long long x ) { return x*(x+1) / 2; } int find( int x ) { if( x != par[x] )par[x] = find( par[x] ); return par[x]; } void uni( int x, int y ) { x = find(x); y = find(y); if( x == y )return; if( i[x] < i[y] )swap( x, y ); par[y] = x; secik.erase( make_pair(need[x], x) ); secik.erase( make_pair(need[y], y) ); Sum2 -= (i[x]-1)*pocz[x]; Sum2 -= (i[y]-1)*pocz[y]; if( x < y ) { sum[x] += sum[y] + pocz[y]; Sum += pocz[y]; nex[x] = nex[y]; } else { sum[x] += sum[y] + pocz[x]; Sum += pocz[x]; pocz[x] = pocz[y]; } Ile -= d(i[x]-1); Ile -= d(i[y]-1); i[x] += i[y]; Ile += d(i[x]-1); Sum2 += (i[x]-1)*pocz[x]; need[x] = ( pocz[find(nex[x])] - pocz[x] ) / i[x]; secik.insert( make_pair( need[x], x ) ); if( len > need[x] )uni( x, nex[x] ); } int main() { ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); cin>>n>>m; for( int a = 0; a <= n+1; a++ ) { par[a] = a; i[a] = 1; sum[a] = 0; nex[a] = a+1; } pocz[n+1] = inf; long long las = 0; pocz[0] = 0; for( int a = 1; a <= n; a++ ) { cin>>x; pocz[a] = x; need[a-1] = x - las; secik.insert( make_pair( x - las, a-1 ) ); las = x; } for( int a = 1; a <= m; a++ ) { cin>>x; tab.push_back( make_pair( x, a ) ); } sort( tab.begin(), tab.end() ); for( int a = 0; a < tab.size(); a++ ) { len = tab[a].first; id = tab[a].second; while( 1 ) { if( secik.size() == 0 )break; it = secik.begin(); if( it->first >= len )break; uni( it->second, nex[it->second] ); } ans[id] = Sum2 + len * Ile - Sum; } for( int a = 1; a <= m; a++ )cout<