제출 #243960

#제출 시각아이디문제언어결과실행 시간메모리
243960uacoder123Foehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
867 ms30584 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; pair<ii,ii> segt[8*100000]; lli lazy[8*100000]; void up(lli node,lli l,lli r,lli s,lli e,lli val) { if(lazy[node]!=0) { segt[node].F.F+=lazy[node]; segt[node].F.S+=lazy[node]; if(l!=r) { lazy[2*node+1]+=lazy[node]; lazy[2*node+2]+=lazy[node]; } lazy[node]=0; } if(l>e||r<s) return; if(l>=s&&r<=e) { segt[node].F.F+=val; segt[node].F.S+=val; if(l!=r) { lazy[2*node+1]+=val; lazy[2*node+2]+=val; } return; } lli m=(l+r)/2; up(2*node+1,l,m,s,e,val); up(2*node+2,m+1,r,s,e,val); segt[node].F.F=segt[2*node+1].F.F; segt[node].F.S=segt[2*node+2].F.S; segt[node].S.F=segt[2*node+1].S.F+segt[2*node+2].S.F; segt[node].S.S=segt[2*node+1].S.S+segt[2*node+2].S.S; if(segt[2*node+1].F.S<=segt[2*node+2].F.F) segt[node].S.F+=segt[2*node+2].F.F-segt[2*node+1].F.S; else segt[node].S.S+=segt[2*node+1].F.S-segt[2*node+2].F.F; } ii qu(lli node,lli l,lli r,lli s,lli e) { if(l>e||r<s) return(mp(0*1LL,0*1LL)); if(lazy[node]!=0) { segt[node].F.F+=lazy[node]; segt[node].F.S+=lazy[node]; if(l!=r) { lazy[2*node+1]+=lazy[node]; lazy[2*node+2]+=lazy[node]; } lazy[node]=0; } if(l>=s&&r<=e) return(segt[node].S); lli m=(l+r)/2; ii q1=qu(2*node+1,l,m,s,e),q2=qu(2*node+2,m+1,r,s,e); return(mp(q1.F+q2.F,q2.S+q1.S)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); lli test=1; for(;test>0;--test) { lli n,q,s,t,fi,se,th; cin>>n>>q>>s>>t; n++; for(lli i=0;i<n;++i) { cin>>fi; up(0,0,n-1,i,i,fi); } for(lli i=0;i<q;++i) { cin>>fi>>se>>th; up(0,0,n-1,fi,se,th); ii ans=qu(0,0,n-1,0,n-1); cout<<-ans.F*s+ans.S*t<<endl; } } return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...