제출 #380360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380360		loctildore	Snowball (JOI21_ho_t2)	C++14	100 / 100	529 ms	13676 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
//#define endl '\n'
#define all(x) begin(x), end(x)
ll n,q,cur,w,day;
ll x[200069],ans[200069],minimum,maximum;
pair<ll,ll> interval[200069];
ll range[200069];
bool dir[200069];//true for right, false for left;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>q;
  for (int i = 0; i < n; i++) {
    cin>>x[i];
  }
  for (int i = 0; i < q; i++) {
    cin>>w;
    cur+=w;
    minimum=min(minimum,cur);
    maximum=max(maximum,cur);
    interval[i]={minimum,maximum};
    range[i]=maximum-minimum;
    dir[i]=(cur>0);
  }
  ans[0]-=minimum;
  ans[n-1]+=maximum;
  for (int i = 0; i < n-1; i++) {
    day=lower_bound(range,range+q,x[i+1]-x[i])-range;
    if (day==q) {
      ans[i]+=maximum;
      ans[i+1]-=minimum;
    }
    else{
      if (dir[day]) {
        ans[i+1]-=max(interval[day].f,x[i]-x[i+1]);
        ans[i]+=max(x[i+1]-x[i]+interval[day].f,(ll)0);
      }
      else{
        ans[i]+=min(interval[day].s,x[i+1]-x[i]);
        ans[i+1]+=max(x[i+1]-x[i]-interval[day].s,(ll)0);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout<<ans[i]<<endl;
  }
  return 0;
}

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