| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 917247 | jamjanek | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
long long c[200010];
struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];
void push(int w){
if(w>=base)return;
tree[w*2].lazy+=tree[w].lazy;
tree[w*2+1].lazy+=tree[w].lazy;
tree[w*2].mini+=tree[w].lazy;
tree[w*2].maxi+=tree[w].lazy;
tree[w*2+1].mini+=tree[w].lazy;
tree[w*2+1].maxi+=tree[w].lazy;
tree[w].lazy = 0;
}
void update(int w, int l, int p, int a, int b, long long val){
push(w);
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w].lazy+=val;
tree[w].maxi+=val;
tree[w].mini+=val;
return;
}
update(w*2, l, (l+p)/2, a, b, val);
update(w*2+1, (l+p)/2+1, p, a, b, val);
tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long maxi(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return -1000000000000000000;
if(a<=l && p<=b){
return tree[w].maxi;
}
return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long mini(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return 1000000000000000000;
if(a<=l && p<=b){
return tree[w].mini;
}
return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
int main()
{
int n, q, i, a, b, v;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &c[i]);
scanf("%d", &q);
vector<pair<int,pair<int,int>>>sorted;
for(i=1;i<=q;i++){
scanf("%d%d%d", &a, &b, &v);
sorted.push_back({a, {i, v}});
sorted.push_back({b+1, {i, -v}});
}
for(i=q+1;i<base;i++){
tree[base+i].mini = 1000000000000000000;
tree[base+i].maxi = -1000000000000000000;
}
for(i=base-1;i>0;i--){
tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
}
sort(sorted.begin(), sorted.end());
int it = 0;
for(i=0;i<n;i++){
while(it<(int)sorted.size() && sorted[it].first==i){
update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
it++;
}
int p;
if(tree[1].maxi-tree[1].mini>=c[i]){
int w = 1;
long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
while(w<base){
push(w);
if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
w = w*2+1;
else{
sufMAX = max(sufMAX, tree[w*2+1].maxi);
sufMIN = min(sufMIN, tree[w*2+1].mini);
w = w*2;
}
}
p = w-base;
}
else{
p = -1;
}
if(p==-1)
printf("%lld ", mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
else{
if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
printf("%lld ", mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
else
printf("%lld ", mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
}
}
}