제출 #896753

#제출 시각아이디문제언어결과실행 시간메모리
896753Muhammad_Aneeq사탕 분배 (IOI21_candies)C++17
11 / 100
5050 ms30804 KiB
#include <vector> #include <cmath> #include <map> #include <algorithm> using namespace std; int const N=2e5+10; int n; struct Seg { int lazy=0,mis=0,mas=0,mif=0,maf=0; }; Seg St[4*N]={};int a[N]={}; void build(int i,int st,int en) { if (st==en) { St[i].mis=St[i].mas=a[st]; St[i].mif=St[i].maf=0; return; } int mid=(st+en)/2; build(i*2,st,mid);build(i*2+1,mid+1,en); St[i].mis=min(St[i*2].mis,St[i*2+1].mis);St[i].mas=max(St[i*2].mas,St[i*2+1].mas); St[i].mif=min(St[i*2].mif,St[i*2+1].mif);St[i].maf=max(St[i*2].maf,St[i*2+1].maf); } void update(int i,int st,int en,int val) { if (val==0) return; if (St[i].mis==St[i].mas) { if (val>0) { int x=min(St[i].mis,val); St[i].lazy+=x; St[i].mis-=x;St[i].mas-=x; St[i].maf+=x;St[i].mif+=x; return; } } if (St[i].mif==St[i].maf) { if (val<0) { int x=min(St[i].mif,abs(val)); x=-x; St[i].lazy+=x; St[i].mis-=x;St[i].mas-=x; St[i].maf+=x;St[i].mif+=x; return; } } if (val>0) { if (St[i].mas==0) return; if (St[i].mis>=val) { St[i].lazy+=val; St[i].mis-=val;St[i].mas-=val; St[i].mif+=val;St[i].maf+=val; return; } } if (val<0) { if (St[i].maf==0) return; if (St[i].mif>=abs(val)) { St[i].lazy+=val; St[i].mis-=val;St[i].mas-=val; St[i].mif+=val;St[i].maf+=val; return; } } int mid=(st+en)/2; update(i*2,st,mid,val+St[i].lazy);update(i*2+1,mid+1,en,val+St[i].lazy); St[i].lazy=0; St[i].mis=min(St[i*2].mis,St[i*2+1].mis);St[i].mas=max(St[i*2].mas,St[i*2+1].mas); St[i].mif=min(St[i*2].mif,St[i*2+1].mif);St[i].maf=max(St[i*2].maf,St[i*2+1].maf); } void update1(int i,int st,int en,int val=0) { if (st==en) { St[i].mif+=val; return; } int mid=(st+en)/2; update1(i*2,st,mid,val+St[i].lazy);update1(i*2+1,mid+1,en,val+St[i].lazy); } int get(int i,int r,int st,int en) { if (st==en) return St[i].mif; int mid=(st+en)/2; if (r<=mid) return get(i*2,r,st,mid); return get(i*2+1,r,mid+1,en); } vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) { n=c.size(); bool w=0; for (auto i:v) if (i<0) w=1; bool subtask_4=1; for (int i=0;i<l.size();i++) { if (l[i]!=0||r[i]!=n-1) subtask_4=0; } if (subtask_4) { map<int,vector<int>>d; for (int i=0;i<n;i++) { a[i]=c[i]; d[a[i]].push_back(i); } sort(a,a+n); build(1,0,n-1); for (auto i:v) update(1,0,n-1,i); update1(1,0,n-1); vector<int>ans(n,0); for (int i=0;i<n;i++) { ans[d[a[i]].back()]=get(1,i,0,n-1); d[a[i]].pop_back(); } return ans; } if (w==0) { vector<long long>d(n+1,0); for (int i=0;i<l.size();i++) { d[l[i]]+=v[i]; d[r[i]+1]-=v[i]; } vector<long long>ans; ans.push_back(d[0]); for (int i=1;i<n;i++) ans.push_back(d[i]+ans.back()); for (int i=0;i<n;i++) { ans[i]=(ans[i]<0?0:ans[i]); ans[i]=min(1ll*c[i],ans[i]); } vector<int>g; g={begin(ans),end(ans)}; return g; } vector<long long>ans(n,0); for (int i=0;i<l.size();i++) { for (int j=l[i];j<=r[i];j++) { ans[j]+=v[i]; ans[j]=min(ans[j],1ll*c[j]); ans[j]=(ans[j]<0?0:ans[j]); } } vector<int>g={begin(ans),end(ans)}; return g; }

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

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~
candies.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int i=0;i<l.size();i++)
      |                      ~^~~~~~~~~
candies.cpp:158:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~
#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...