제출 #534838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534838		Paul_Liao_1457	Snowball (JOI21_ho_t2)	C++14	100 / 100	392 ms	17928 KiB

Main

// 還要更強
#include<iostream>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<math.h>
#include<cstring>
#include<stack>
#include<string.h>
#include<random>
#include<algorithm>
#include<vector>

#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define INF (ll)(3e18)
#define pb push_back
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

int n,q;
vector<ll> v,Q,p1,p2,s1,s2;
vector<pair<ll,pair<ll,ll> > >  ya1,ya2;

ll ans[200005];

signed main(){
    AC;
    cin>>n>>q;
    v.pb(-INF);
    FOR(i,0,n){
        ll x; cin>>x;
        v.pb(x);
    }
    v.pb(INF);
    FOR(i,0,q){
        ll y; cin>>y;
        Q.pb(y);
    }
    ll now=0,maxn=0,minn=0;
    FOR(j,0,q){
        now+=Q[j]; maxn=max(maxn,now); minn=min(minn,now);
        if(now<0) ya1.pb({maxn-now,{-now,maxn}});
        if(now>0) ya2.pb({now-minn,{now,-minn}});
    }
    sort(ya1.begin(),ya1.end());
    sort(ya2.begin(),ya2.end());
    maxn=0;
    for(auto i:ya1){
        maxn=max(maxn,i.S.F);
        p1.pb(maxn);
    }
    maxn=0;
    for(auto i:ya2){
        maxn=max(maxn,i.S.F);
        p2.pb(maxn);
    }
    minn=INF;
    for(int i=(int)ya1.size()-1;i>=0;i--){
        minn=min(minn,ya1[i].S.S);
        s1.pb(minn);
    }
    minn=INF;
    for(int i=(int)ya2.size()-1;i>=0;i--){
        minn=min(minn,ya2[i].S.S);
        s2.pb(minn);
    }
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    
    FOR(i,1,n+1){
        ll l=0,r=(int)ya1.size();
        ll len1=v[i]-v[i-1],len2=v[i+1]-v[i],maxn=-1;
        while(l<r){
            ll mid=(l+r)>>1;
            if(ya1[mid].F<=len1){
                maxn=max(maxn,mid); l=mid+1;
            }
            else{
                r=mid;
            }
        }
        ll pos=v[i];
        if(maxn!=-1) pos=min(pos,v[i]-p1[maxn]);
        if(maxn+1<s1.size()) pos=min(pos,v[i-1]+s1[maxn+1]);
        ans[i]+=v[i]-pos;
        l=0; r=(int)ya2.size(); maxn=-1;
        while(l<r){
            ll mid=(l+r)>>1;
            if(ya2[mid].F<=len2){
                maxn=max(maxn,mid); l=mid+1;
            }
            else{
                r=mid;
            }
        }
        pos=v[i];
        if(maxn!=-1) pos=max(pos,v[i]+p2[maxn]);
        if(maxn+1<s2.size()) pos=max(pos,v[i+1]-s2[maxn+1]);
        ans[i]+=pos-v[i];
    }
    FOR(i,1,n+1) cout<<ans[i]<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:90:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if(maxn+1<s1.size()) pos=min(pos,v[i-1]+s1[maxn+1]);
      |            ~~~~~~^~~~~~~~~~
Main.cpp:104:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if(maxn+1<s2.size()) pos=max(pos,v[i+1]-s2[maxn+1]);
      |            ~~~~~~^~~~~~~~~~

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