# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
288311 | NemanjaSo2005 | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define LIMIT 7000000
using namespace std;
ll koliko[200005],povecaj,res=0,T,S,N,Q,u1,u2,r1,r2,r3,r4,segmentno[400010];
char buffer[LIMIT],*pos;
ll nadji(int gde){
ll ret=0;
while(gde){
ret+=segmentno[gde];
gde/=2;
}
return ret;
}
void dodaj(int gde,int lb,int db,int l,int r){
if(lb>db or l>r)
return;
if(lb==l and db==r){
segmentno[gde]+=povecaj;
return;
}
int mid=(l+r)/2;
dodaj(gde*2,lb,mid,l,min(mid,r));
dodaj(gde*2+1,mid+1,db,max(l,mid+1),r);
return;
}
ll getll(){
ll positive=1,number;
while(*pos!='-' and *pos<48)
*pos++;
if(*pos=='-'){
*pos++;
positive=-1;
}
else positive=1;
number=*pos-'0';
*pos++;
while(*pos>=48){
number=number*10+*pos-'0';
*pos++;
}
return positive*number;
}
int main(){
/*fread(buffer,1,LIMIT,stdin);
pos=buffer;
N=getll();
Q=getll();
S=getll();
T=getll();*/
cin>>N>>Q>>S>>T;
N++;
if(N<=5000){
for(int i=1;i<=N;i++)
cin>>koliko[i];//koliko[i]=getll();
for(int i=1;i<N;i++)
if(koliko[i]<koliko[i+1])
res-=S*abs(koliko[i]-koliko[i+1]);
else res+=T*abs(koliko[i]-koliko[i+1]);
// cout<<res<<endl;
while(Q--){
cin>>u1;//u1=getll();
cin>>u2;//u2=getll();
cin>>povecaj;//povecaj=getll();
u1++;
u2++;
r1=koliko[u1-1];
r2=koliko[u1];
r3=koliko[u2];
r4=koliko[u2+1];
if(u1!=1){
if(r1<r2)
res+=(r2-r1)*S;
else res-=(r1-r2)*T;
}
if(u2!=N){
if(r3<r4)
res+=(r4-r3)*S;
else res-=(r3-r4)*T;
}
// cout<<res<<endl;
for(int i=u1;i<=u2;i++)
koliko[i]+=povecaj;
r2+=povecaj;
r3+=povecaj;
if(u1!=1){
if(r1<r2)
res-=(r2-r1)*S;
else res+=(r1-r2)*T;
}
if(u2!=N){
if(r3<r4)
res-=(r4-r3)*S;
else res+=(r3-r4)*T;
}
/* for(int i=1;i<=N;i++)
cout<<koliko[i]<<" ";
cout<<endl;*/
cout<<res<<endl;
}
return 0;
}
for(int i=1;i<=N;i++)
cin>>koliko[i]//koliko[i]=getll();
for(int i=1;i<N;i++)
if(koliko[i]<koliko[i+1])
res-=S*abs(koliko[i]-koliko[i+1]);
else res+=T*abs(koliko[i]-koliko[i+1]);
// cout<<res<<endl;
while(Q--){
cin>>u1;//u1=getll();
cin>>u2;//u2=getll();
cin>>povecaj;//povecaj=getll();
u1++;
u2++;
r1=nadji(u1-1+N);
r2=nadji(u1+N);
r3=nadji(u2+N);
r4=nadji(u2+1+N);
if(u1!=1){
if(r1<r2)
res+=(r2-r1)*S;
else res-=(r1-r2)*T;
}
if(u2!=N){
if(r3<r4)
res+=(r4-r3)*S;
else res-=(r3-r4)*T;
}
// cout<<res<<endl;
dodaj(1,u1,u2,1,N);
r2+=povecaj;
r3+=povecaj;
if(u1!=1){
if(r1<r2)
res-=(r2-r1)*S;
else res+=(r1-r2)*T;
}
if(u2!=N){
if(r3<r4)
res-=(r4-r3)*S;
else res+=(r3-r4)*T;
}
/* for(int i=1;i<=N;i++)
cout<<koliko[i]<<" ";
cout<<endl;*/
cout<<res<<endl;
}
return 0;
}