제출 #851113

#제출 시각아이디문제언어결과실행 시간메모리
851113CSQ31사탕 분배 (IOI21_candies)C++17
29 / 100
2133 ms83344 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]; int n,q; 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 -1e18; 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+1,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; ll cursum = 0; void solve(int v,int tl,int tr){ for(auto x:ch[v]){ upd(1,x.fi,q,0,q,x.se); cursum+=x.se; } if(tl==tr){ int l = 0,r = q; //cout<<tl<<" "<<mnn[1]<<" "<<mxx[1]<<'\n'; while(r>=l){ int mid = (l+r)/2; ll rmn = mnquery(1,mid,q,0,q); ll rmx = mxquery(1,mid,q,0,q); if(rmx - rmn< C[tl])r = mid-1; else l = mid+1; } if(r==-1){ ans[tl] = cursum - mnn[1]; return; } ll a = mnquery(1,r,q,0,q); ll b = mxquery(1,r,q,0,q); if(mnquery(1,r,r,0,q) == a)ans[tl] = C[tl] - (b - cursum); else ans[tl] = cursum - a; for(auto x:ch[v]){ upd(1,x.fi,q,0,q,-x.se); cursum-=x.se; } return; } int tm = (tl+tr)/2; solve(2*v,tl,tm); solve(2*v+1,tm+1,tr); for(auto x:ch[v]){ upd(1,x.fi,q,0,q,-x.se); cursum-=x.se; } } vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){ n = sz(c); 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...