제출 #940966

#제출 시각아이디문제언어결과실행 시간메모리
9409667mody사탕 분배 (IOI21_candies)C++17
100 / 100
2612 ms51284 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; struct seg{ int sz = 1; vector<ll>mn,mx,sum,op,add; seg(int n){ while(sz < n) sz*=2; mn.assign(sz*2,0ll); mx.assign(sz*2,0ll); op.assign(sz*2,0ll); sum.assign(sz*2,0ll); add.assign(sz*2,0ll); } void push(int x,int lx,int rx){ if(rx-lx == 1) return; int m = (lx+rx)/2; add[x*2+1] += add[x]; add[x*2+2] += add[x]; sum[x*2+1] += add[x] * (m-lx); sum[x*2+2] += add[x] * (rx-m); sum[x] = sum[x*2+1] + sum[x*2+2]; add[x] = 0; } void update(int l,int r,ll v,int x=0,int lx=0,int rx=-1){ if(rx == -1){r++;rx=sz;} push(x,lx,rx); if(rx <= l || lx >= r) return; if(rx <= r && lx >= l){ op[x] += v; mn[x] += v; mx[x] += v; add[x] += v; sum[x] += (rx-lx)*v; return; } int m = (lx+rx)/2; update(l,r,v,x*2+1,lx,m); update(l,r,v,x*2+2,m,rx); mn[x] = min(mn[x*2+1] , mn[x*2+2]) + op[x]; mx[x] = max(mx[x*2+1] , mx[x*2+2]) + op[x]; sum[x] = sum[x*2+1] + sum[x*2+2];} ll getMIN(int l,int r,int x=0,int lx=0,int rx=-1){ if(rx == -1){rx=sz;r++;} if(rx <= l || lx >= r) return 1e15; if(rx <= r && lx >= l) return mn[x]; int m = (lx+rx)/2; return min(getMIN(l,r,x*2+1,lx,m),getMIN(l,r,x*2+2,m,rx)) + op[x];} ll getMAX(int l,int r,int x=0,int lx=0,int rx=-1){ if(rx == -1){rx=sz;r++;} if(rx <= l || lx >= r) return -1e15; if(rx <= r && lx >= l) return mx[x]; int m = (lx+rx)/2; return max(getMAX(l,r,x*2+1,lx,m),getMAX(l,r,x*2+2,m,rx)) + op[x];} ll getSUM(int l,int r,int x=0,int lx=0,int rx=-1){ if(rx == -1){rx=sz;r++;} push(x,lx,rx); if(rx <= l || lx >= r) return 0ll; if(rx <= r && lx >= l) return sum[x]; int m = (lx+rx)/2; return getSUM(l,r,x*2+1,lx,m)+getSUM(l,r,x*2+2,m,rx);}}; int n, m; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){ n = c.size(); m = r.size(); vector<int> s(n); vector<vector<int>> L(n),R(n); for(int i=0; i < m;i++){ L[l[i]].push_back(i); R[r[i]].push_back(i); } seg st(m + 2); // - 0 , for(int i=0; i < n;i++){ for(int x : L[i]) st.update(x + 2, m + 1, v[x]); int l = 0; int r = m; int id = -1; ll cmx, cmn = st.getMIN(1, m + 1); while(l <= r){ int mid = (l+r)/2; ll a,b; a = st.getMAX(mid + 1, m + 1), b = st.getMIN(mid + 1, m + 1); if(a - b >= c[i]){ l = mid+1; id = mid; cmx = a; cmn = b; } else r = mid-1; } // cout << cmx << ' ' << cmn << endl; if(id == -1){ s[i] = st.getSUM(m+1,m+1) - cmn; for(int x : R[i]) st.update(x + 2, m + 1, -v[x]); continue; } int cond = 0; ll curr; id++; if(cmx == st.getMAX(id + 1, m + 1)) cond = 1, curr = cmx; else cond = 0, curr = cmn; if(cond){ int l = id - 1; int r = m; while(l <= r){ int mid = (l+r)/2; if(st.getMAX(mid + 1, m + 1) == curr){ id = mid; l = mid + 1; } else r = mid - 1; } id++; // cout << st.getSUM(id + 1, m + 1) << ' ' << id << ' '; s[i] = c[i] - (st.getSUM(id, id) - st.getSUM(m+1,m+1)); } else{ int l = id - 1; int r = m; while(l <= r){ int mid = (l+r)/2; if(st.getMIN(mid + 1, m + 1) == curr){ id = mid; l = mid + 1; } else r = mid - 1; } id++; s[i] = st.getSUM(m+1,m+1) - st.getSUM(id, id); } for(int x : R[i]) st.update(x + 2, m + 1, -v[x]); } return s; }
#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...