Submission #57881

#	Time	Username	Problem	Language	Result	Execution time	Memory
57881		BrunoPloumhans	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	294 ms	161916 KiB

foehn_phenomena

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

#define int long long
#define D(x) //cout << #x << ": " << x << endl

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{ ";
  for(const T& t : v)
    os << t << ", ";
  return os << "}";
}

template<typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& v) {
  return os << "{ " << v.first << ", " << v.second << " }";
}

int ft1[200002];
int n, s, t;
// point query, range update
int query1(int i) {
  int sum = 0;
  for(; i > 0; i -= (i&(-i)))
    sum += ft1[i];
  return sum;
}

void update1(int i, int w) {
  for(; i <= n+1; i+=(i&(-i)))
    ft1[i] += w;
}

void update1(int a, int b, int w) {
  update1(a, w);
  update1(b+1, -w);
}

int sm = 0;

int diff(int a, int b) {
  return a > b ? (a-b)*t : (a-b)*s;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int q;
  cin >> n >> q >> s >> t;

  int prev;
  for(int i = 0; i <= n; ++i) {
    int a;
    cin >> a;
    update1(i+1, i+1, a);
    if(i != 0) {
      sm += diff(prev, a);
      D(diff(prev, a));
    }
    prev = a;
  }
  D(sm);

  for(int i = 0; i < q; ++i) {
    int l, r, x;
    cin >> l >> r >> x;
    int a1 = query1(l), a2 = query1(l+1);
    D(sm);
    sm -= diff(a1, a2);
    sm += diff(a1, a2+x);
    D(sm);
    if(r != n) {
      int b1 = query1(r+1), b2 = query1(r+2);
      sm -= diff(b1, b2);
      sm += diff(b1+x, b2);
      D(sm);
    }
    update1(l+1, r+1, x);
    /*    for(int i = 0; i <= n; ++i)
      cout << query1(i+1) << " ";
      cout << "\n";*/
    D("next");
    cout << sm << "\n";
  }

  return 0;
}

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