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
#include <cstdio>
#include <algorithm>
using namespace std;
int i,j,n,m,x;

  long long ileTypa[200006];
  long long moment[200006];

long long klient[200006],ost,czekaj,suma,piec,kolejka[200006],maxTypa;
//int piec[200006];
int main() {
    scanf(" %d %d",&n,&m);
    for(i=0;i<n;i++){
        scanf(" %I64d",&klient[i]);//moment przyjscia klienta
    }
    klient[i++]=0x9184E72A000LL;
    //printf("tutaj");
    sort(klient,klient+i);
    //printf("jestem");


    x=0,maxTypa=0;
    for(i=0;i<n;i++){
        int ile=0;

        while(klient[i]==klient[i+1]) {
            ile++;
            i++;
            //printf("^");
            if (ile>maxTypa)
                maxTypa= ile;
        }
        ileTypa[x]=ile;
        moment[x++]=klient[i];
    }

    for(i=0;i<m;i++){
        ost=0LL;suma=0LL;
        long long spacja;
        scanf(" %I64d",&piec);
        //inicjuj tablice czasow przychodzenia klientow w jednym momencie - optymalizacja
        kolejka[0] = 0LL;
        //kolejka[1] = piec;
        maxTypa++;
     /*
        for(j=1;j<=maxTypa;j++){
            kolejka[j]=kolejka[j-1]+ j*piec;
            //printf("! %I64d",kolejka[j]);
        }
    */
        //printf("\n");
        //printf("maxTypa:%d\n",maxTypa);
        for(j=0;j<x;j++){
            spacja = moment[j]-ost;
            //printf("spacja:%I64d\n",spacja);
            czekaj = 0LL;
            if(spacja>0){
                if(spacja<piec){
                    czekaj += piec - spacja;
                    //wszystkie osoby musza poczekac zanim odbierze pierwsza
                    suma += czekaj * ileTypa[j] + czekaj;
                }
                if(ileTypa[j] > 0){
                    czekaj += ileTypa[j] * piec;
                    //suma += kolejka[ ileTypa[j] ];
                    suma+= ((piec + ileTypa[j]*piec )*ileTypa[j])/2;
                }
                ost = moment[j] + czekaj;
                //printf("cz:%I64d ost:%I64d\n",czekaj,ost);
                //suma += czekaj;
            }else if (spacja<=0) {
                czekaj = ileTypa[j] * piec + piec;
                ost += czekaj;
                //suma += kolejka[ ileTypa[j] +1];
                suma+= ((piec + (ileTypa[j]+1)*piec )*(ileTypa[j]+1))/2;
                //printf("tgyh");
            }

        }
        printf("%I64d\n",suma);
    }

    return 0;
}