제출 #851094

#제출 시각아이디문제언어결과실행 시간메모리
851094CSQ31사탕 분배 (IOI21_candies)C++17
3 / 100
5103 ms72064 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound typedef long long int ll; const int MAXN = 2e5+5; ll mnn[4*MAXN],mxx[4*MAXN],lazy[4*MAXN],ans[MAXN],C[MAXN]; void upd(int v,int l,int r,int tl,int tr,ll val){ if(l==tl && r==tr){ lazy[v]+=val; mnn[v]+=val; mxx[v]+=val; return; } int tm = (tl+tr)/2; if(r<=tm)upd(2*v,l,r,tl,tm,val); else if(l>tm)upd(2*v+1,l,r,tm+1,tr,val); else{ upd(2*v,l,tm,tl,tm,val); upd(2*v+1,tm+1,r,tm+1,tr,val); } mnn[v] = min(mnn[2*v],mnn[2*v+1])+lazy[v]; mxx[v] = max(mxx[2*v],mxx[2*v+1])+lazy[v]; } ll mnquery(int v,int l,int r,int tl,int tr){ if(l>r)return 1e18; if(l==tl && r==tr)return mnn[v]; int tm = (tl+tr)/2; return min(mnquery(2*v,l,min(r,tm),tl,tm), mnquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v]; } ll mxquery(int v,int l,int r,int tl,int tr){ if(l>r)return 0; if(l==tl && r==tr)return mxx[v]; int tm = (tl+tr)/2; return max(mxquery(2*v,l,min(r,tm),tl,tm), mxquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v]; } vector<pair<int,int>>ch[4*MAXN]; void add(int v,int l,int r,int tl,int tr,int t,ll val){ if(l>r)return; if(l==tl && r==tr){ ch[v].pb({t,val}); return; } int tm = (tl+tr)/2; add(2*v,l,min(r,tm),tl,tm,t,val); add(2*v+1,max(tm+1,l),r,tm+1,tr,t,val); } set<pair<int,int>>cur; void solve(int v,int tl,int tr){ for(auto x:ch[v])cur.insert(x); if(tl==tr){ vector<ll>p = {0}; ans[tl] = 0; for(auto x:cur){ ans[tl]+=x.se; ans[tl] = max(ans[tl],0LL); ans[tl] = min(ans[tl],C[tl]); } /* ll mn = 1e18; ll mx = -1e18; for(int i=sz(p)-1;i>=0;i--){ mn = min(mn,p[i]); mx = max(mx,p[i]); if(mx-mn >= C[tl]){ if(p[i]==mn)ans[tl] = C[tl] - (mx - p.back()); else ans[tl] = p.back() - mn; break; } } if(mx-mn < C[tl])ans[tl] = p.back()-mn; * */ for(auto x:ch[v])cur.erase(x); return; } int tm = (tl+tr)/2; solve(2*v,tl,tm); solve(2*v+1,tm+1,tr); for(auto x:ch[v])cur.erase(x); } vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){ int n = sz(c); int q = sz(l); for(int i=0;i<n;i++)C[i] = c[i]; for(int i=0;i<q;i++)add(1,l[i],r[i],0,n-1,i,v[i]); solve(1,0,n-1); vector<int>tmp(n); for(int i=0;i<n;i++)tmp[i] = ans[i]; return tmp; }
#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...