oj.uz

Submission #647652

# Submission time Handle Problem Language Result Execution time Memory
647652 2022-10-03T13:40:56 Z mosiashvililuka Measures (CEOI22_measures) C++14
100 / 100
 649 ms 35992 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 649 ms 31760 KB Output is correct
10 Correct 594 ms 33028 KB Output is correct
11 Correct 220 ms 19868 KB Output is correct
12 Correct 302 ms 32640 KB Output is correct
13 Correct 308 ms 32260 KB Output is correct
14 Correct 286 ms 32204 KB Output is correct
15 Correct 577 ms 32252 KB Output is correct
16 Correct 291 ms 31764 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 32656 KB Output is correct
2 Correct 302 ms 35624 KB Output is correct
3 Correct 208 ms 23004 KB Output is correct
4 Correct 304 ms 32916 KB Output is correct
5 Correct 293 ms 34808 KB Output is correct
6 Correct 295 ms 33856 KB Output is correct
7 Correct 297 ms 35072 KB Output is correct
8 Correct 301 ms 34052 KB Output is correct
9 Correct 281 ms 33432 KB Output is correct
10 Correct 345 ms 35992 KB Output is correct
11 Correct 286 ms 34276 KB Output is correct
12 Correct 300 ms 35292 KB Output is correct
13 Correct 287 ms 33200 KB Output is correct
14 Correct 288 ms 35556 KB Output is correct
15 Correct 304 ms 35048 KB Output is correct
16 Correct 275 ms 33356 KB Output is correct
17 Correct 306 ms 34764 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 32656 KB Output is correct
2 Correct 302 ms 35624 KB Output is correct
3 Correct 208 ms 23004 KB Output is correct
4 Correct 304 ms 32916 KB Output is correct
5 Correct 293 ms 34808 KB Output is correct
6 Correct 295 ms 33856 KB Output is correct
7 Correct 297 ms 35072 KB Output is correct
8 Correct 301 ms 34052 KB Output is correct
9 Correct 281 ms 33432 KB Output is correct
10 Correct 345 ms 35992 KB Output is correct
11 Correct 286 ms 34276 KB Output is correct
12 Correct 300 ms 35292 KB Output is correct
13 Correct 287 ms 33200 KB Output is correct
14 Correct 288 ms 35556 KB Output is correct
15 Correct 304 ms 35048 KB Output is correct
16 Correct 275 ms 33356 KB Output is correct
17 Correct 306 ms 34764 KB Output is correct
18 Correct 583 ms 34384 KB Output is correct
19 Correct 524 ms 35648 KB Output is correct
20 Correct 223 ms 23636 KB Output is correct
21 Correct 296 ms 33872 KB Output is correct
22 Correct 508 ms 34444 KB Output is correct
23 Correct 288 ms 34124 KB Output is correct
24 Correct 605 ms 34552 KB Output is correct
25 Correct 294 ms 34028 KB Output is correct
26 Correct 536 ms 33716 KB Output is correct
27 Correct 568 ms 35740 KB Output is correct
28 Correct 455 ms 34292 KB Output is correct
29 Correct 472 ms 34280 KB Output is correct
30 Correct 313 ms 33092 KB Output is correct
31 Correct 290 ms 35540 KB Output is correct
32 Correct 361 ms 34672 KB Output is correct
33 Correct 576 ms 32360 KB Output is correct
34 Correct 290 ms 34336 KB Output is correct