Submission #605842

#	Time	Username	Problem	Language	Result	Execution time	Memory
605842		jjiangly	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	159 ms	13140 KiB

foehn_phenomena

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

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf LLONG_MAX

const int nxm = int(2e5) + 7;
ll n, q, s, t, a[nxm];

namespace sub1 {
  ll l, r, x;
  void exe() {
    while (q--) {
      cin >> l >> r >> x;
      for (int i = l; i <= r; ++i) {
        a[i] += x;
      }
      ll ans = 0;
      for (int i = 1; i <= n; ++i) {
        if (a[i] > a[i - 1]) {
          ans -= (a[i] - a[i - 1]) * s;
        } else {
          ans += (a[i - 1] - a[i]) * t;
        }
      }
      cout << ans << "\n";
    }
  }
};

namespace sub2 {
  ll l, r, x;
  ll bit[nxm];
  void add(int x, ll v) {
    for (int i = x + 1; i <= nxm; i += i & -i) {
      bit[i - 1] += v;
    }
  }
  ll sum(int x) {
    ll r = 0;
    for (int i = x; i > 0; i -= i & -i) {
      r += bit[i - 1];
    }
    return r;
  }
  void exe() {
    ll Sum = 0;
    for (int i = 1; i <= n; ++i) {
      Sum += (a[i] - a[i - 1]);
    }
    while (q--) {
      cin >> l >> r >> x;
      Sum -= a[l] + sum(l + 1) - a[l - 1] - sum(l);
      if (r + 1 <= n) {
        Sum -= a[r + 1] + sum(r + 2) - a[r] - sum(r + 1);
      }
      add(l, x);
      add(r + 1, -x);
      Sum += a[l] + sum(l + 1) - a[l - 1] - sum(l);
      if (r + 1 <= n) {
        Sum += a[r + 1] + sum(r + 2) - a[r] - sum(r + 1);
      }
      cout << Sum * (-t) << "\n";
    }
  }
};

namespace sub3 {
  ll l, r, x;
  ll bit[nxm];
  void add(int x, ll v) {
    for (int i = x + 1; i <= nxm; i += i & -i) {
      bit[i - 1] += v;
    }
  }
  ll sum(int x) {
    ll r = 0;
    for (int i = x; i > 0; i -= i & -i) {
      r += bit[i - 1];
    }
    return r;
  }
  void exe() {
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
       if (a[i] > a[i - 1]) {
         ans -= (a[i] - a[i - 1]) * s;
       } else {
         ans += (a[i - 1] - a[i]) * t;
       }
    }
    //cout << ans << "\n";
    while (q--) {
      cin >> l >> r >> x;
      ll rhs = a[l] + sum(l + 1);
      ll lhs = a[l - 1] + sum(l);
      if (rhs > lhs) {
        ans += (rhs - lhs) * s;
      } else {
        ans -= (lhs - rhs) * t;
      }
      if (r + 1 <= n) {
        rhs = a[r + 1] + sum(r + 2);
        lhs = a[r] + sum(r + 1);
        if (rhs > lhs) {
          ans += (rhs - lhs) * s;
        } else {
          ans -= (lhs - rhs) * t;
        }
      }
      add(l, x);
      add(r + 1, -x);
      rhs = a[l] + sum(l + 1);
      lhs = a[l - 1] + sum(l);
      if (rhs > lhs) {
        ans -= (rhs - lhs) * s;
      } else {
        ans += (lhs - rhs) * t;
      }
      if (r + 1 <= n) {
        rhs = a[r + 1] + sum(r + 2);
        lhs = a[r] + sum(r + 1);
        if (rhs > lhs) {
          ans -= (rhs - lhs) * s;
        } else {
          ans += (lhs - rhs) * t;
        }
      }
      cout << ans << "\n";
    }
  }
};

int subtask() {
  if (n <= 2000 && q <= 2000) {
    return 1;
  } else if (s == t) {
    return 2;
  }
  return 3;
}

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

  cin >> n >> q >> s >> t;
  for (int i = 0; i <= n; ++i) {
    cin >> a[i];
  }
  if (subtask() == 1) {
    sub1::exe();
  } else if (subtask() == 2) {
    sub2::exe();
  } else {
    sub3::exe();
  }

  return 0;
}

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