Submission #443483

#TimeUsernameProblemLanguageResultExecution timeMemory
443483leinad2Distributing Candies (IOI21_candies)C++17
100 / 100
2923 ms38436 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; long long mx[800010], mn[800010], lazy[800010], inf=9000000000000000000; vector<pair<int, int> >upd[200010]; void busy(int id) { lazy[id*2]+=lazy[id]; lazy[id*2+1]+=lazy[id]; mx[id*2]+=lazy[id]; mx[id*2+1]+=lazy[id]; mn[id*2]+=lazy[id]; mn[id*2+1]+=lazy[id]; lazy[id]=0; } void update(int id, int s, int e, int l, int r, int v) { if(e<l||r<s)return; if(l<=s&&e<=r) { mx[id]+=v; mn[id]+=v; lazy[id]+=v; return; } int m=s+e>>1;busy(id); update(id*2, s, m, l, r, v);update(id*2+1, m+1, e, l, r, v); mx[id]=max(mx[id*2], mx[id*2+1]); mn[id]=min(mn[id*2], mn[id*2+1]); } long long get1(int id, int s, int e, int l, int r) { if(e<l||r<s)return -inf; if(l<=s&&e<=r)return mx[id]; int m=s+e>>1;busy(id); return max(get1(id*2, s, m, l, r), get1(id*2+1, m+1, e, l, r)); } long long get2(int id, int s, int e, int l, int r) { if(e<l||r<s)return inf; if(l<=s&&e<=r)return mn[id]; int m=s+e>>1;busy(id); return min(get2(id*2, s, m, l, r), get2(id*2+1, m+1, e, l, r)); } vector<int>distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int>v) { int n=C.size(), q=l.size(), i, j, k, a, b; vector<long long>c;for(i=0;i<n;i++)c.push_back(C[i]); for(i=0;i<q;i++) { upd[l[i]].push_back({v[i], i}); upd[r[i]+1].push_back({-v[i], i}); } vector<int>ans;ans.resize(n); for(i=0;i<n;i++) { for(j=0;j<upd[i].size();j++) { a=upd[i][j].first;b=upd[i][j].second; update(1, 1, q+1, b+2, q+1, a); } long long x=get1(1, 1, q+1, 1, q+1)-get2(1, 1, q+1, 1, q+1); if(x<=c[i])ans[i]=get1(1, 1, q+1, q+1, q+1)-get2(1, 1, q+1, 1, q+1); else { int a=1, b=q+1; while(a<b) { int m=a+b+1>>1; if(get1(1, 1, q+1, m, q+1)-get2(1, 1, q+1, m, q+1)<=c[i])b=m-1; else a=m; } if(get1(1, 1, q+1, a, a)<get2(1, 1, q+1, a+1, q+1)) { ans[i]=c[i]-get1(1, 1, q+1, a+1, q+1)+get1(1, 1, q+1, q+1, q+1); } else { ans[i]=get1(1, 1, q+1, q+1, q+1)-get2(1, 1, q+1, a+1, q+1); } } } return ans; }

Compilation message (stderr)

candies.cpp: In function 'void update(int, int, int, int, int, int)':
candies.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'long long int get1(int, int, int, int, int)':
candies.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'long long int get2(int, int, int, int, int)':
candies.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(j=0;j<upd[i].size();j++)
      |                 ~^~~~~~~~~~~~~~
candies.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |                 int m=a+b+1>>1;
      |                       ~~~^~
candies.cpp:47:39: warning: unused variable 'k' [-Wunused-variable]
   47 |     int n=C.size(), q=l.size(), i, j, k, a, b;
      |                                       ^
#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...