[noi1994]海盗

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 2000005
 4 #define ll long long
 5 #define pii pair<int,int>
 6 #define fi first
 7 #define se second 
 8 #define s(p) son[k][p]
 9 int V,n,r,x,tag,tot[N],sz[N],ra[N],son[N][2];
10 ll k,ans,a[N],f[N];
11 void up(int k){
12     sz[k]=sz[s(0)]+sz[s(1)]+tot[k];
13     f[k]=1LL*a[k]*tot[k]+f[s(0)]+f[s(1)];
14 }
15 void rotate(int &k,int u,int p){
16     s(p)=son[u][p^1];
17     son[u][p^1]=k;
18     up(k);
19     k=u;
20 }
21 void add(int &k,ll x,int y){
22     if (!k){
23         k=++V;
24         a[k]=f[k]=x;
25         ra[k]=rand();
26     }
27     if (a[k]==x){
28         tot[k]+=y;
29         up(k);
30         return;
31     }
32     bool p=(a[k]<x);
33     add(s(p),x,y);
34     if (ra[s(p)]<ra[k])rotate(k,s(p),p);
35     up(k);
36 }
37 ll query(int k,int x){
38     if (!k)return 0;
39     if (x<=sz[s(0)])return query(s(0),x);
40     if (x<=sz[s(0)]+tot[k])return f[s(0)]+1LL*a[k]*(x-sz[s(0)]);
41     return f[s(0)]+1LL*a[k]*tot[k]+query(s(1),x-sz[s(0)]-tot[k]);
42 }
43 void del(int &k,int x){
44     if (!k)return;
45     if (x<=sz[s(0)])del(k=s(0),x);
46     else
47         if (x>sz[s(0)]+tot[k])del(s(1),x-sz[s(0)]-tot[k]);
48         else{
49             tot[k]-=sz[s(0)]+tot[k]-x;
50             s(1)=0;
51         }
52     up(k);
53 }
54 int main(){
55     scanf("%d%lld",&n,&k);
56     for(int i=1;i<=n;i++){
57         scanf("%d",&x);
58         ans=max(k-(query(r,x-1)+(x-1LL)*(tag+1)),-1LL);
59         if (ans!=-1){
60             int s=sz[r]-(x-1);
61             del(r,x-1);
62             tag++;
63             add(r,-tag,s);
64         }
65         add(r,ans-tag,1);
66         printf("%lld\n",ans);
67     }
68 }