| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 996371 | cpdreamer | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define V vector
typedef long long ll;
struct segtree{
private:
struct node{
ll sum;
int len;
};
node neutral={0LL,0};
static node merge(node a,node b){
return {a.sum+b.sum,a.len+b.len};
}
static node modification(node a,ll v){
return {a.sum+a.len*v,a.len};
}
static ll operation_modifier(ll a,ll v){
return a+v;
}
public:
int size;
V<node>query;
V<ll>operation;
void init(int n){
size=1;
while(size<n)size*=2;
query.assign(2*size,{0LL,1});
operation.assign(2*size,0LL);
}
void build(int x,int lx,int rx){
if(rx-lx==1)
return;
int m=(lx+rx)/2;
build(2*x+1,lx,m);
build(2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void build(){
build(0,0,size);
}
void set(int l,int r,int v,int x,int lx,int rx){
if(lx>=r || rx<=l)
return ;
if(l<=lx && rx<=r){
query[x]= modification(query[x],v);
operation[x]= operation_modifier(operation[x],v);
return;
}
int m=(lx+rx)/2;
set(l,r,v,2*x+1,lx,m);
set(l,r,v,2*x+2,m,rx);
query[x]= modification(merge(query[2*x+1],query[2*x+2]),operation[x]);
}
void set(int l,int r,int v){
set(l,r,v,0,0,size);
}
node calc(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l)
return neutral;
if(l<=lx && rx<=r)
return query[x];
int m=(lx+rx)/2;
node a=calc(l,r,2*x+1,lx,m);
node b=calc(l,r,2*x+2,m,rx);
return modification(merge(a,b),operation[x]);
}
ll calc(int l,int r){
return calc(l,r,0,0,size).sum;
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
int n = (int)c.size();
std::vector<int> s(n);
segtree tree;
tree.init(n);
tree.build();
for(int i=0;i<(int)l.size();i++){
tree.set(l[i],r[i]+1,v[i]);
}
for(int i=0;i<n;i++){
s[i]=(int)min(tree.calc(i,i+1),(ll)c[i]);
}
return s;
}