Submission #871098

#	Time	Username	Problem	Language	Result	Execution time	Memory
871098		Maite_Morale	Snowball (JOI21_ho_t2)	C++14	0 / 100	3 ms	6608 KiB

Main

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>

ll n,q,a[MAX],qry[MAX],mx[MAX],mn[MAX];
ll bs(ll x){
    ll p=0,f=q;//cout<<x;
    while(abs(p-f)!=1){
        ll m=(p+f)/2;//cout<<m<<" "<<mx[m]<<"+"<<-mn[m]<<"\n";
        if(mx[m]-mn[m]>x)f=m;
        else             p=m;
    }
return p;
}
int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<q;i++){
        cin>>qry[i];
        if(i==0){
            mx[i]=max((ll)0,qry[i]);
            mn[i]=min((ll)0,qry[i]);
            continue;
        }qry[i]+=qry[i-1];
        mx[i]=max(mx[i-1],qry[i]);
        mn[i]=min(mn[i-1],qry[i]);
    }
    for(int i=0;i<n;i++){
        ll r=0;
        if(i==0)r+=-mn[q-1];
        else{
            ll x=bs(a[i]-a[i-1]);//cout<<x<<" ";
            if(x==q-1)r+=-mn[q-1];
            else     if(-mn[x]<-mn[x+1])r+=a[i]-a[i-1]-mx[x];
                     else               r+=-mn[x];
        }//cout<<r<<" ";
        if(i==n-1)r+=mx[q-1];
        else{
            ll x=bs(a[i+1]-a[i]);//cout<<x<<" ";
            if(x==q-1)r+=mx[q-1];
            else     if(mx[x]<mx[x+1])r+=a[i+1]-a[i]+mn[x];
                     else             r+=mx[x];
        }cout<<r<<"\n";
    }

return 0;
}

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