Submission #647652

#	Time	Username	Problem	Language	Result	Execution time	Memory
647652		mosiashvililuka	Measures (CEOI22_measures)	C++14	100 / 100	649 ms	35992 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,NN,M,D,f[400009],pas,fen[400009],seg[2000009],segmn[2000009],segmx[2000009],seg2[2000009],l,r,z,za;
map <long long, long long> m;
map <long long, long long>::iterator IT;
void updfen(long long q, long long w){
    while(q<=400003){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
long long readfen(long long q){
    long long sm=0;
    while(q>0){
        sm+=fen[q];
        q=q-(q&(-q));
    }
    return sm;
}
void GETrr(long long rr){
    segmx[rr]=max(segmx[rr*2],segmx[rr*2+1]);
    segmn[rr]=min(segmn[rr*2],segmn[rr*2+1]);

    seg[rr]=max(seg[rr*2],seg[rr*2+1]);
    seg[rr]=max(seg[rr],segmx[rr*2]-segmn[rr*2+1]);
}
void UP(long long rr){
    rr/=2;
    while(rr!=0){
        GETrr(rr);
        rr/=2;
    }
}
void pushdown(long long q, long long w, long long rr){
    if(q!=w){
        seg2[rr*2]+=seg2[rr];
        seg2[rr*2+1]+=seg2[rr];
    }
    segmn[rr]+=seg2[rr];segmx[rr]+=seg2[rr];
    seg2[rr]=0;
}
void upd(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]+=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    GETrr(rr);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>NN>>M>>D;a=NN+M;
    for(i=1; i<=a; i++){
        cin>>f[i];
        m[f[i]]++;
    }
    za=1;
    while(za<a) za*=2;
    for(i=0; i<=za*2+1; i++){
        segmn[i]=N;segmx[i]=-N;seg[i]=0;
    }
    zx=0;
    for(IT=m.begin(); IT!=m.end(); IT++){
        xc=(*IT).second;
        (*IT).second=zx;zx+=xc;
    }
    for(ii=1; ii<=a; ii++){
        m[f[ii]]++;
        i=m[f[ii]];
        //cout<<f[ii]<<" "<<i<<"\n";
        //
        l=i;r=i;z=0;
        upd(1,za,1);
        c=readfen(i);updfen(i,1);
        segmn[za+i-1]=segmx[za+i-1]=f[ii]-c*D;seg[za+i-1]=0;
        UP(za+i-1);
        //
        /*for(i=1; i<=za*2-1; i++){
            cout<<i<<":     "<<seg[i]<<" "<<segmn[i]<<" "<<segmx[i]<<" "<<seg2[i]<<"\n";
        }
        cout<<"\n\n";*/
        l=i;r=a;z=-D;
        upd(1,za,1);
        //
        /*for(i=1; i<=za*2-1; i++){
            cout<<i<<":     "<<seg[i]<<" "<<segmn[i]<<" "<<segmx[i]<<" "<<seg2[i]<<"\n";
        }
        cout<<"ii\n\n";*/
        pushdown(1,za,1);
        pas=seg[1];
        if(ii<=NN) continue;
        if(pas%2==0){
            cout<<pas/2<<" ";
        }else{
            cout<<pas/2<<".5 ";
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41