Submission #686644

#	Time	Username	Problem	Language	Result	Execution time	Memory
686644		Pacybwoah	Snowball (JOI21_ho_t2)	C++14	100 / 100	236 ms	13644 KiB

Main

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    ll n,q;
    cin>>n>>q;
    vector<ll> vec(n);
    for(int i=0;i<n;i++) cin>>vec[i];
    vector<ll> wind(q);
    for(int i=0;i<q;i++) cin>>wind[i];
    for(int i=1;i<q;i++) wind[i]+=wind[i-1];
    vector<ll> newind;
    bool sign=(wind[0]>0);
    if(wind[0]==0){
        for(int i=1;i<q;i++){
            if(wind[i]!=0){
                sign=(wind[i]>0);
                break;
            }
        }
    }
    ll curmax=wind[0];
    for(int i=1;i<q;i++){
        if(sign==1&&wind[i]>=0){
            curmax=max(curmax,wind[i]);
        }
        else if(sign==0&&wind[i]<=0){
            curmax=min(curmax,wind[i]);
        }
        else{
            newind.push_back(curmax);
            sign=(!sign);
            curmax=wind[i];
        }
    }
    if(curmax!=0) newind.push_back(curmax);
    ll maxpos=-1,maxneg=0,tmp=newind.size();
    vector<pair<ll,ll>> fin;
    ll curind=-1;
    for(int i=0;i<tmp;i++){
        if(newind[i]<0){
            maxneg=min(maxneg,newind[i]);
        }
        else{
            if(newind[i]>maxpos){
                if(curind>=0&&fin[curind].second==maxneg) fin[curind].first=newind[i];
                else fin.push_back(make_pair(newind[i],maxneg)),curind++;
                maxpos=newind[i];
            }
        }
    }
    ll len=fin.size(),curr,curl=vec[0]+maxneg;
    bool flag=1;
    for(auto x:wind) if(x>0) flag=0;
    if(flag){
        for(int i=0;i<n;i++){
            cout<<vec[i]-curl<<"\n";
            if(i!=n-1) curl=max(vec[i],vec[i+1]+maxneg);
        }
        return 0;
    }
    //for(auto x:fin) cout<<x.first<<" "<<x.second<<"\n";
    for(int i=0;i<n-1;i++){
        ll dist=vec[i+1]-vec[i];
        curl=max(curl,vec[i]+maxneg);
        if(fin[0].first>=dist+fin[0].second){
            cout<<max(dist+fin[0].second,(ll)0)+vec[i]-curl<<"\n";
            curl=max(dist+fin[0].second,(ll)0)+vec[i];
            continue;
        }
        ll l=0,r=len-1,ans=0;
        if(l==r){
            ans=max(ans,min(fin[0].first,dist+fin[0].second));
        }
        while(l<r){
            ll mid=(l+r)>>1;
            if(min(fin[mid].first,dist+fin[mid].second)>min(fin[mid+1].first,dist+fin[mid+1].second)){
                r=mid;
                ans=max(ans,min(fin[mid].first,dist+fin[mid].second));
            }
            else if(min(fin[mid].first,dist+fin[mid].second)==min(fin[mid+1].first,dist+fin[mid+1].second)){
                l=mid,r=mid;
                ans=max(ans,min(fin[mid].first,dist+fin[mid].second));
            }
            else{
                l=mid+1;
                ans=max(ans,min(fin[mid+1].first,dist+fin[mid+1].second));
            }
                        //cout<<l<<" "<<r<<" "<<ans<<"\n";
        }
        cout<<ans+vec[i]-curl<<"\n";
        //cout<<ans+vec[i]<<" "<<curl<<"\n";
        curl=ans+vec[i];
    }
    cout<<vec[n-1]+maxpos-max(curl,vec[n-1]+maxneg);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:55:23: warning: unused variable 'curr' [-Wunused-variable]
   55 |     ll len=fin.size(),curr,curl=vec[0]+maxneg;
      |                       ^~~~

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