이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
ll val[500003];
void aos(int l , int r , ll c , int x , int lx , int rx){
if(lx >= l && rx <= r){
val[x] += c;
return;
}
if(r <= lx || l >= rx)return;
int m = (lx + rx)/2;
val[2 * x + 1] += val[x];
val[2 * x + 2] += val[x];
aos(l ,r , c , 2 * x + 1 , lx , m);
aos(l , r , c , 2 * x + 2 , m, rx);
}
ll find(int i , int x , int lx , int rx){
if(rx - lx == 1)return val[x];
int m = (lx + rx)/2;
val[2 * x + 1] += val[x];
val[2 * x + 2] += val[x];
val[x] = 0;
if(i < m){
return find(i , 2 * x + 1 , lx , m);
}
else return find(i , 2 * x + 2 , m , rx);
}
void solve(){
ll n , q , s , t;
cin >> n >> q >> s >> t;
int siz = 1;
while(siz < n)siz*=2;
memset(val,0,sizeof val);
ll arr[n + 1];
for(int i = 0; i <= n; i++)cin >> arr[i];
ll ans = 0;
for(int i = 1; i <= n; i++){
if(arr[i-1] < arr[i]){
ans -= (arr[i] - arr[i-1]) * s;
}
else ans += (arr[i-1] - arr[i]) * t;
}
while(q--){
int l, r;
ll x;
cin >> l >> r >> x;
ll curl = arr[l] + find(l , 0 , 0 , siz);
ll curr = arr[r] + find(r , 0 , 0 , siz);
ll pre , next;
if(l == 1)pre = 0;
else pre = arr[l-1] + find(l - 1 , 0 , 0, siz);
if(r == n)next = 1e18;
else next = arr[r + 1] + find(r + 1 , 0 , 0 , siz);
if(curl > pre)ans += (curl - pre) * s;
else ans -= (pre - curl) * t;
if(next != 1e18){
if(next > curr)ans += (next - curr) * s;
else ans -= (curr- next) * t;
}
aos(l , r + 1 , x , 0 , 0 , siz);
curl += x;
curr += x;
if(curl > pre)ans -= (curl - pre) * s;
else ans += (pre - curl) * t;
if(next != 1e18){
if(next > curr)ans -= (next - curr) * s;
else ans += (curr- next) * t;
}
cout << ans << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
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... |