Submission #501142

#TimeUsernameProblemLanguageResultExecution timeMemory
501142shahriarkhanSnowball (JOI21_ho_t2)C++14
100 / 100
1872 ms13760 KiB
#include<bits/stdc++.h> using namespace std ; const int MX = 2e5 + 5 ; const long long INF = 1e18 + 5 ; long long pref_mx[MX] , pref_mn[MX] ; int n , q ; int smaller_equal(long long val) { if(pref_mn[q]>val) return (q+1) ; int low = 0 , high = q ; while(low<high) { int mid = (low+high)>>1 ; if(pref_mn[mid]<=val) high = mid ; else low = mid + 1 ; } return low ; } int bigger_equal(long long val) { if(pref_mx[q]<val) return (q+1) ; int low = 0 , high = q ; while(low<high) { int mid = (low+high)>>1 ; if(pref_mx[mid]>=val) high = mid ; else low = mid + 1 ; } return low ; } int main() { scanf("%d%d",&n,&q) ; long long x[n+2] , sum = 0 , ans[n+1] = {0} ; for(int i = 1 ; i <= n ; ++i) { scanf("%lld",&x[i]) ; } pref_mx[0] = 0 , pref_mn[0] = INF ; for(int i = 1 ; i <= q ; ++i) { long long cur ; scanf("%lld",&cur) ; sum += cur ; pref_mx[i] = max(pref_mx[i-1],sum) ; pref_mn[i] = min(pref_mn[i-1],sum) ; } for(int i = 1 ; i <= n ; ++i) { long long low = 0 , high = INF , left = 0 , right = 0 ; while(low<high) { long long mid = (low+high+1)>>1 ; if(i==n) { int pos = bigger_equal(mid) ; if(pos>q) high = mid - 1 ; else low = mid ; } else { if((x[i]+mid)>x[i+1]) high = mid - 1 ; else if(bigger_equal(mid)<smaller_equal(x[i]-x[i+1]+mid-1)) low = mid ; else high = mid - 1 ; } } left = low ; low = 0 , high = INF ; while(low<high) { long long mid = (low+high+1)>>1 ; if(i==1) { int pos = smaller_equal(-mid) ; if(pos>q) high = mid - 1 ; else low = mid ; } else { if((x[i]-mid)<x[i-1]) high = mid - 1 ; else if(smaller_equal(-mid)<bigger_equal(x[i]-x[i-1]-mid+1)) low = mid ; else high = mid - 1 ; } } right = low ; ans[i] = left+right ; } for(int i = 1 ; i <= n ; ++i) { printf("%lld\n",ans[i]) ; } return 0 ; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld",&x[i]) ;
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld",&cur) ;
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...