제출 #164814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164814		cbertram	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1041 ms	6584 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)

ll fenGet(vll& arr, ll i) {
  ll sum = 0;
  for(i++; i > 0; i -= i&-i)
    sum += arr[i];
  return sum;
}
void fenAdd(vll& arr, ll i, ll a) {
  for(i++; i < (int)arr.size(); i += i&-i)
    arr[i] += a;
}

int main() {
  ll N, Q, S, T;
  cin >> N;
  cin >> Q;
  cin >> S;
  cin >> T;
  vll fenT((N+2)*2);
  vll Ad(N+2);
  ll last = 0;
  rep(n,0,N+1) {
    ll a;
    cin >> a;
    Ad[n] = a-last;
    last = a;
  }
  rep(n,1,N+1) {
    ll diff = Ad[n];
    fenAdd(fenT, n, diff > 0 ? -diff*S : -diff*T);
  }
  rep(q,0,Q) {
    ll L, R, X;
    cin >> L;
    cin >> R;
    cin >> X;

    ll diff = Ad[L];
    fenAdd(fenT, L, diff > 0 ? diff*S : diff*T);
    diff = Ad[R+1];
    fenAdd(fenT, R+1, diff > 0 ? diff*S : diff*T);
    
    Ad[L]   += X;
    Ad[R+1] -= X;

    diff = Ad[L];
    fenAdd(fenT, L, diff > 0 ? -diff*S : -diff*T);
    diff = Ad[R+1];
    fenAdd(fenT, R+1, diff > 0 ? -diff*S : -diff*T);
    
    cout << fenGet(fenT, N) << '\n';
  }
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60