Submission #486183

#	Time	Username	Problem	Language	Result	Execution time	Memory
486183		bigDuck	Snowball (JOI21_ho_t2)	C++14	100 / 100	117 ms	16880 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
inline char get_ (){
    const int oo=1000005;
    static char buf[oo], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++;
}
int read_ () {
    char c = get_();
    int sum = 0;
    while(!(c >= '0' && c <= '9')) c = get_();
    while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_();
    return sum;
}



int n, x[300010], q;
int w[300010];

int ww[300010], we[300010], sw[300010];


int wt[300010];


int32_t main(){
INIT

cin>>n>>q;
for(int i=1; i<=n; i++){
    cin>>x[i];
}


int ac=0;

for(int i=1; i<=q; i++){
    cin>>w[i];
    ww[i]=ww[i-1];
    we[i]=we[i-1];
    ac+=w[i];
    if(ac<0){
        ww[i]=max(ww[i], -ac);
    }
    else{
        we[i]=max(we[i], ac);
    }
    sw[i]=we[i]+ww[i];
}


//dont forget maxwest and maxeast for endpoints
sort(x+1, x+1+n);
for(int i=1; i<n; i++){
    //first sw>x[i+1]-x[i];
    int l=1, r=q+1, m=(l+r)>>1ll;
    while(l<r){
        m=(l+r)>>1ll;
        if(sw[m]>(x[i+1]-x[i]) ){
            r=m;
        }
        else{
            l=(m+1);
        }
        m=(l+r)>>1ll;
    }
    wt[i]+=we[m-1];
    wt[i+1]+=ww[m-1];
    if( (m<=q)   ){
        if(w[m]<0){
            if( sw[m]>(x[i+1]-x[i]) ){wt[i+1]+=x[i+1]-x[i]-we[m-1]-ww[m-1];}
        }
        else{
            if( sw[m]>(x[i+1]-x[i]) ){wt[i]+=x[i+1]-x[i]-ww[m-1]-we[m-1];}
        }
    }
}

int me=0, mw=0;
ac=0;
for(int i=1; i<=q; i++){
    ac+=w[i];
    if(ac<0){
        mw=max(mw, -ac);
    }
    else{
        me=max(me, ac);
    }
}
wt[1]+=mw;
wt[n]+=me;


for(int i=1; i<=n; i++){
    cout<<wt[i]<<"\n";
}

return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67