| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 940728 | 7mody | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #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;
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){
l = 0;
r = m;
int limit = st.getMIN(1, m + 1);
while(l <= r){
int mid = (l + r)/2;
if(st.getMIN(mid + 1, m + 1) == limit){
l = mid + 1;
id = mid;
} else r = mid - 1;
} id++;
s[i] = st.getSUM(m+1,m+1) - st.getSUM(id,id);
// 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;
}
void solve(){
cin >> n;
vector<int> c(n);
for(int i=0; i < n;i++) cin >> c[i];
int q; cin >> q;
vector<int> l(q),r(q),v(q);
for(int i=0; i < q;i++) cin >> l[i];
for(int i=0; i < q;i++) cin >> r[i];
for(int i=0; i < q;i++) cin >> v[i];
vector<int> ans = distribute_candies(c,l,r,v); cout << endl;
for(int x : ans) cout << x << ' '; cout << endl;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int t=1;
// cin >> t;
while(t--){
// cout << t << ":\n";
solve();
}
}