제출 #624202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624202		Abrar_Al_Samit	Snowball (JOI21_ho_t2)	C++17	33 / 100	920 ms	13752 KiB

Main

#include<bits/stdc++.h>
using namespace std;

const long long oo = 1e13;

void PlayGround() {
  int n, q;
  cin>>n>>q;
  long long a[n];
  for(int i=0; i<n; ++i) {
    cin>>a[i];
  }

  long long pre[q+1] = {0};
  for(int i=1; i<=q; ++i) {
    cin>>pre[i];
  }
  for(int i=1; i<=q; ++i) {
    pre[i] += pre[i-1];
  }

  long long premn[q+1], premx[q+1];
  premx[0] = premn[0] = pre[0];
  for(int i=1; i<=q; ++i) {
    premx[i] = max(premx[i-1], pre[i]);
    premn[i] = min(premn[i-1], pre[i]);

  }

  long long ans[n] = {0};
  for(int i=0; i<n; ++i) {
    long long r = a[i];
    long long l = -oo;

    while(l<r) {
      long long mid;
      if(l<0 && r<=0) mid = (l+r-1)/2;
      else mid = (l+r)/2;

      if(premn[q]+a[i]>mid) {
        l = mid+1;
        continue;
      }
      int lid = 0, rid = q;
      while(lid<rid) {
        int midid = (lid+rid)/2;
        if(premn[midid]+a[i]<=mid) {
          rid = midid;
        } else {
          lid = midid+1;
        }
      }
      if(lid && i) {
        if(premx[lid-1]+a[i-1]>mid) {
          l = mid+1;
        } else {
          r = mid;
        }
      } else {
        r = mid;
      }
    }

    ans[i] += a[i]-l;


    l = a[i];
    r = oo;
    while(l<r) {
      long long mid = (1+l+r)/2;

      if(premx[q]+a[i]<mid) {
        r = mid-1;
        continue;
      }

      int lid = 0, rid = q;
      while(lid<rid) {
        int midid = (lid+rid)/2;

        if(a[i]+premx[midid]>=mid) {
          rid = midid;
        } else {
          lid = midid+1;
        }
      }
      if(lid && i<n-1) {
        if(premn[lid-1]+a[i+1]<mid) {
          r = mid-1;
        } else {
          l = mid;
        }
      } else {
        l = mid;
      }
    }
    ans[i] += l-a[i];
  }

  for(int i=0; i<n; ++i) {
    cout<<ans[i]<<'\n';
  }

}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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