제출 #536191

#제출 시각아이디문제언어결과실행 시간메모리
536191groshiFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
212 ms14688 KiB
#include<iostream> using namespace std; int pot=1; long long drzewo[500000]; long long a[300000]; void dodaj(int x,int y,long long ile) { x+=pot; y+=pot; drzewo[x]+=ile; if(x!=y) drzewo[y]+=ile; while(x/2!=y/2) { if(x%2==0) drzewo[x+1]+=ile; if(y%2==1) drzewo[y-1]+=ile; x/=2; y/=2; } } long long zap(int x) { x+=pot; long long wynik=0; wynik+=drzewo[x]; x/=2; while(x>0) { wynik+=drzewo[x]; x/=2; } return wynik; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); long long n,q,s,t,x,y,z; cin>>n>>q>>s>>t; for(int i=1;i<=n+1;i++) cin>>a[i]; while(pot<=n) pot*=2; pot--; for(int i=1;i<=n+1;i++) drzewo[i+pot]=a[i]; long long wynik=0; for(int i=2;i<=n+1;i++) { if(a[i]>a[i-1]) wynik-=(a[i]-a[i-1])*s; else wynik+=(a[i-1]-a[i])*t; } while(q--) { cin>>x>>y>>z; x++; y++; dodaj(x,y,z); long long nowy_x=zap(x); long long nowy_y=zap(y); //if(x>1) //{ long long x_1=zap(x-1); long long stary_x=nowy_x-z; if(stary_x>x_1) wynik+=(stary_x-x_1)*s; else wynik-=(x_1-stary_x)*t; if(nowy_x>x_1) wynik-=(nowy_x-x_1)*s; else wynik+=(x_1-nowy_x)*t; //} if(y<n+1) { long long y_1=zap(y+1); long long stary_y=nowy_y-z; if(y_1>stary_y) wynik+=(y_1-stary_y)*s; else wynik-=(stary_y-y_1)*t; if(y_1>nowy_y) wynik-=(y_1-nowy_y)*s; else wynik+=(nowy_y-y_1)*t; } cout<<wynik<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...