Submission #624205

#	Time	Username	Problem	Language	Result	Execution time	Memory
624205		Abrar_Al_Samit	Snowball (JOI21_ho_t2)	C++17	100 / 100	849 ms	15348 KiB

Main

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

const long long oo = 1e18;

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: 67 / 67