Submission #164808

#	Time	Username	Problem	Language	Result	Execution time	Memory
164808		cbertram	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1077 ms	19544 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 fenA((N+2)*4);
  vll fenT((N+2)*4);
  rep(n,0,N+1) {
    ll a;
    cin >> a;
    fenAdd(fenA, n, a);
    fenAdd(fenA, n+1, -a);
  }
  rep(n,1,N+1) {
    ll diff = fenGet(fenA, n)-fenGet(fenA, n-1);
    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 = fenGet(fenA, L)-fenGet(fenA, L-1);
    fenAdd(fenT, L, diff > 0 ? diff*S : diff*T);
    diff = fenGet(fenA, R+1)-fenGet(fenA, R);
    fenAdd(fenT, R+1, diff > 0 ? diff*S : diff*T);
    
    fenAdd(fenA, L, X);
    fenAdd(fenA, R+1, -X);

    diff = fenGet(fenA, L)-fenGet(fenA, L-1);
    fenAdd(fenT, L, diff > 0 ? -diff*S : -diff*T);
    diff = fenGet(fenA, R+1)-fenGet(fenA, R);
    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