제출 #614151

#제출 시각아이디문제언어결과실행 시간메모리
614151krit3379사탕 분배 (IOI21_candies)C++17
100 / 100
1584 ms45328 KiB
#include<bits/stdc++.h> #include"candies.h" using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define N 200005 struct SegmentTree{ int n,ll,rr; long long mi[4*N],ma[4*N],lazy[4*N],val; void init(int _n){ n=_n; for(int i=0;i<4*N;i++)mi[i]=ma[i]=lazy[i]=0; } void push(int x){ if(lazy[x]){ if(x<2*N){ lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x]; } mi[x]+=lazy[x]; ma[x]+=lazy[x]; lazy[x]=0; } } void upd(int x,int l,int r){ push(x); if(l>rr||ll>r)return ; if(ll<=l&&r<=rr){ lazy[x]+=val; push(x); return ; } int mid=(l+r)/2; upd(x*2,l,mid); upd(x*2+1,mid+1,r); mi[x]=min(mi[x*2],mi[x*2+1]); ma[x]=max(ma[x*2],ma[x*2+1]); } void upd(int x,long long v){ ll=x,rr=n,val=v; upd(1,1,n); } long long min_val(int x,int l,int r,int p){ push(x); if(p>r)return 1e18; if(l>=p)return mi[x]; int mid=(l+r)/2; return min(min_val(x*2,l,mid,p),min_val(x*2+1,mid+1,r,p)); } long long min_val(int x){ return min_val(1,1,n,x); } long long max_val(int x,int l,int r,int p){ push(x); if(p>r)return -1e18; if(l>=p)return ma[x]; int mid=(l+r)/2; return max(max_val(x*2,l,mid,p),max_val(x*2+1,mid+1,r,p)); } long long max_val(int x){ return max_val(1,1,n,x); } long long point_val(int x,int l,int r,int p){ push(x); if(l>p||p>r)return 0; if(l==r)return ma[x]; int mid=(l+r)/2; return point_val(x*2,l,mid,p)+point_val(x*2+1,mid+1,r,p); } long long point_val(int x){ return point_val(1,1,n,x); } }st; vector<int> ans; vector<pair<int,int>> op[N]; vector<int> distribute_candies(vector<int> C,vector<int> L,vector<int> R,vector<int> V){ int n=C.size(),q=L.size(),i,l,r,mid,pos; ans.resize(n); for(i=0;i<q;i++){ op[L[i]].push_back({i+2,V[i]}); op[R[i]+1].push_back({i+2,-V[i]}); } st.init(q+1); for(i=0;i<n;i++){ for(auto [x,v]:op[i])st.upd(x,v); long long m1=st.max_val(0),m2=st.min_val(0); if(m1-m2<C[i]){ ans[i]=st.max_val(q+1)-m2; continue; } l=0,r=q+1; while(l<=r){ mid=(l+r)/2; m1=st.max_val(mid),m2=st.min_val(mid); if(m1-m2>=C[i])pos=mid,l=mid+1; else r=mid-1; } long long v1=st.point_val(pos),v2=st.max_val(q+1); m1=st.max_val(pos),m2=st.min_val(pos); if(v1==m1)ans[i]=v2-m2; else ans[i]=C[i]-(m1-v2); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:46:9: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |         if(p>r)return 1e18;
      |         ^~
candies.cpp:82:41: note: 'pos' was declared here
   82 |     int n=C.size(),q=L.size(),i,l,r,mid,pos;
      |                                         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...