Submission #1100723

#TimeUsernameProblemLanguageResultExecution timeMemory
1100723quannnguyen2009Snowball (JOI21_ho_t2)C++17
100 / 100
83 ms16972 KiB
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define pb push_back #define ii pair<int, int> #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() using namespace std; const int N=2e5+5, mod = 1e9+7, inf = 1e18; int n, q; int a[N], res[N], dif[N], p[N], mn[N], ma[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i=1; i<=n; i++) { cin >> a[i]; if(i>1) dif[i-1] = a[i]-a[i-1]; } for(int i=1; i<=q; i++) { int x; cin >> x; p[i] = p[i-1] + x; mn[i] = min(mn[i-1], p[i]); ma[i] = max(ma[i-1], p[i]); } for(int i=1; i<n; i++) { int l=1, r=q, ans; while(l<=r) { int mid = (l+r)>>1; if(ma[mid]-mn[mid]>=dif[i]) { ans = mid; r = mid-1; } else l = mid+1; } if(ma[q]-mn[q]<dif[i]) { res[i]+=ma[q]; res[i+1]-=mn[q]; continue; } ans--; res[i]+=ma[ans]; res[i+1]-=mn[ans]; l=a[i]+ma[ans]; r=a[i+1]+mn[ans]; ans++; if(p[ans]>0) res[i]+=r-l; else res[i+1]+=r-l; } res[1]-=mn[q]; res[n]+=ma[q]; for(int i=1; i<=n; i++) cout << res[i] << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |         ans--;
      |         ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...