//PRZEMYSL ASSERTY //SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE //MODULO = 1 #include <cstdio> #include <cstring> #include <cassert> #include <cmath> #include <algorithm> #include <queue> #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define FORD(i,a,b) for(int i=(a);i>=(b);--i) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define e1 first #define e2 second #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; int n,m,ile[200001],fl[200001],fp[200001],tr[1<<19]; ll s1,st,dod,t[200001],ans[200001]; pli roz[200001]; pii d[200001]; int find(int a) { if (fl[a]==-1) return a; fl[a]=find(fl[a]); return fl[a]; } void Union(int a,int b) { int xa=find(a),xb=find(b); xa==xb?0:fl[xa]=xb; } int find2(int a) { if (!fp[a]) return a; fp[a]=find2(fp[a]); return fp[a]; } void Union2(int a,int b) { int xa=find2(a),xb=find2(b); xa==xb?0:fp[xa]=xb; } ll licz(int x) { return (ll)x*(x+1)/2; } void ustaw(int a,pli x) { roz[a]=x; a=(a+(1<<18))>>1; while (a) { int nl=tr[a+a],np=tr[a+a+1]; //printf("%d %d %lld-%d %lld-%d\n",a,tr[a],roz[nl].e1,roz[nl].e2,roz[np].e1,roz[np].e2); if (roz[nl]==mp(0ll,0)) { tr[a]=np; a>>=1; continue; } if (roz[np]==mp(0ll,0)) { tr[a]=nl; a>>=1; continue; } ll w1=roz[nl].e1*roz[np].e2; ll w2=roz[np].e1*roz[nl].e2; tr[a]=w1<w2?nl:np; a>>=1; } } int main() { scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%lld",&t[i]),tr[i+(1<<18)]=i,ustaw(i,mp(t[i]-t[i-1],1)),st+=t[i]; FOR(i,1,m) scanf("%d",&d[i].e1),d[i].e2=i; sort(d+1,d+m+1); fill(fl,fl+n+1,-1); s1=st; int zos=n; FOR(i,1,m) { while (zos>0 && roz[tr[1]].e1<=(ll)roz[tr[1]].e2*d[i].e1) { int nr=tr[1]; Union(nr,nr-1); if (nr>0) Union2(nr-1,nr); s1+=(t[find(nr)]-t[nr])*(ile[nr]+1); dod-=licz(ile[nr])+licz(ile[find(nr)]); ile[find(nr)]+=ile[nr]+1; dod+=licz(ile[find(nr)]); int pk=find2(nr); if (pk!=n) ustaw(pk+1,mp(t[pk+1]-t[find(nr)],pk+1-find(nr))); ustaw(nr,mp(0,0)); zos--; } ans[d[i].e2]=s1+dod*d[i].e1-st; } FOR(i,1,m) printf("%lld\n",ans[i]); }
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 | //PRZEMYSL ASSERTY //SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE //MODULO = 1 #include <cstdio> #include <cstring> #include <cassert> #include <cmath> #include <algorithm> #include <queue> #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define FORD(i,a,b) for(int i=(a);i>=(b);--i) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define e1 first #define e2 second #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; int n,m,ile[200001],fl[200001],fp[200001],tr[1<<19]; ll s1,st,dod,t[200001],ans[200001]; pli roz[200001]; pii d[200001]; int find(int a) { if (fl[a]==-1) return a; fl[a]=find(fl[a]); return fl[a]; } void Union(int a,int b) { int xa=find(a),xb=find(b); xa==xb?0:fl[xa]=xb; } int find2(int a) { if (!fp[a]) return a; fp[a]=find2(fp[a]); return fp[a]; } void Union2(int a,int b) { int xa=find2(a),xb=find2(b); xa==xb?0:fp[xa]=xb; } ll licz(int x) { return (ll)x*(x+1)/2; } void ustaw(int a,pli x) { roz[a]=x; a=(a+(1<<18))>>1; while (a) { int nl=tr[a+a],np=tr[a+a+1]; //printf("%d %d %lld-%d %lld-%d\n",a,tr[a],roz[nl].e1,roz[nl].e2,roz[np].e1,roz[np].e2); if (roz[nl]==mp(0ll,0)) { tr[a]=np; a>>=1; continue; } if (roz[np]==mp(0ll,0)) { tr[a]=nl; a>>=1; continue; } ll w1=roz[nl].e1*roz[np].e2; ll w2=roz[np].e1*roz[nl].e2; tr[a]=w1<w2?nl:np; a>>=1; } } int main() { scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%lld",&t[i]),tr[i+(1<<18)]=i,ustaw(i,mp(t[i]-t[i-1],1)),st+=t[i]; FOR(i,1,m) scanf("%d",&d[i].e1),d[i].e2=i; sort(d+1,d+m+1); fill(fl,fl+n+1,-1); s1=st; int zos=n; FOR(i,1,m) { while (zos>0 && roz[tr[1]].e1<=(ll)roz[tr[1]].e2*d[i].e1) { int nr=tr[1]; Union(nr,nr-1); if (nr>0) Union2(nr-1,nr); s1+=(t[find(nr)]-t[nr])*(ile[nr]+1); dod-=licz(ile[nr])+licz(ile[find(nr)]); ile[find(nr)]+=ile[nr]+1; dod+=licz(ile[find(nr)]); int pk=find2(nr); if (pk!=n) ustaw(pk+1,mp(t[pk+1]-t[find(nr)],pk+1-find(nr))); ustaw(nr,mp(0,0)); zos--; } ans[d[i].e2]=s1+dod*d[i].e1-st; } FOR(i,1,m) printf("%lld\n",ans[i]); } |