이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
using namespace std;
struct SegmentTree {
struct Node {
int height;
int pending_change;
};
vector<Node> tree;
int n;
SegmentTree(int size) {
n=size;
tree.resize(4*n);
build(0,0,n-1);
}
void build(int v,int tl,int tr) {
if(tl==tr) {
tree[v]={0,0};
} else {
int tm=(tl+tr)/2;
build(v*2+1, tl,tm);
build(v*2+2, tm+1,tr);
tree[v]={0,0};
}
}
void update(int v,int tl,int tr,int l,int r,int change) {
if(l>r) return;
if(tl==l&&tr==r) {
tree[v].pending_change+=change;
} else {
int tm=(tl+tr)/2;
update(v*2+1,tl,tm,l,min(r,tm),change);
update(v*2+2,tm+1,tr,max(l,tm+1),r,change);
}
}
int get_temperature(int v,int tl,int tr,int position,int temperature) {
if(tl==tr) {
return temperature+tree[v].pending_change;
} else {
int tm=(tl+tr)/2;
if(position<=tm) {
return get_temperature(v*2+1,tl,tm,position,temperature+tree[v].pending_change);
} else {
return get_temperature(v*2+2,tm+1,tr,position,temperature+tree[v].pending_change);
}
}
}
void process_movement(int L,int R,int X) {
update(0,0,n-1,L,R,X);
}
};
int main() {
int N,Q,S,T;
cin>>N>>Q>>S>>T;
vector<int> A(N+1);
for(int i=1; i<=N; ++i) {
cin>>A[i];
}
SegmentTree st(N+1);
for(int day=0; day<Q; ++day) {
int L,R,X;
cin>>L>>R>>X;
st.process_movement(L,R,X);
int wind_temperature=0;
for(int i=1; i<=N; ++i) {
int height_current=st.get_temperature(0,0,N-1,i,0);
int height_previous=st.get_temperature(0,0,N-1,i-1,0);
if(height_current>height_previous) {
wind_temperature-=S*(height_current-height_previous);
} else if(height_current<height_previous) {
wind_temperature+=T*(height_previous-height_current);
}
}
cout<<wind_temperature<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |