제출 #232729

#제출 시각아이디문제언어결과실행 시간메모리
232729jiahngFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
161 ms9208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pi; typedef vector <ll> vi; typedef vector <pi> vpi; #define f first #define s second #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0) #define maxn 200101 #define int ll int N,Q,S,T; int fw[maxn],A[maxn]; void update(int p,int v){ //update position p by +=v for (int i=p; i<=N+10; i+= (i&(-i))){ fw[i] += v; } } void upd(int a,int b, int c){ //update position a to b by +=c update(a,c); //upd function from the PURQ fenwick update(b+1,-c); } int qry(int p){ //query p int ans = 0; for (int i = p; i>0; i -= (i&(-i))){ ans += fw[i]; } return ans; } int32_t main(){ fast; cin>>N>>Q>>S>>T; FOR(i,0,N){ cin>>A[i]; if (i != 0) upd(i,i,A[i]); } int cur = 0; FOR(i,0,N-1){ if (A[i] < A[i+1]) cur -= S * (A[i+1] - A[i]); else cur += T * (A[i] - A[i+1]); } FOR(i,1,Q){ int a,b,c; cin>>a>>b>>c; int Aval = qry(a); int Aprev = qry(a-1); int Bval = qry(b); if (Aprev < Aval) cur += S * (Aval - Aprev); else cur -= T * (Aprev - Aval); Aval += c; if (Aprev < Aval) cur -= S * (Aval - Aprev); else cur += T * (Aprev - Aval); if (b+1 <= N){ int Bnext = qry(b+1); if (Bval < Bnext) cur += S * (Bnext - Bval); else cur -= T * (Bval - Bnext); Bval += c; if (Bval < Bnext) cur -= S * (Bnext - Bval); else cur += T * (Bval - Bnext); } cout<<cur<<'\n'; upd(a,b,c); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...