Submission #780408

#	Time	Username	Problem	Language	Result	Execution time	Memory
780408		myde	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	96 ms	11480 KiB

foehn_phenomena

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

const int maxn = 2e5;
int n, q, s, t, sumS = 0, sumT = 0;
int bit[maxn + 5];
int ls(int x) { return x & (-x); }

void upd(int x, int val)
{
  for (int i = x; i <= maxn; i += ls(i))
    bit[i] += val;
}

int get(int x)
{
  int res = 0;
  for (int i = x; i > 0; i -= ls(i))
    res += bit[i];
  return res;
}

int get(int l, int r)
{
  return get(r) - get(l - 1);
}

void updSum(int idx, int type)
{
  if (bit[idx] > 0)
    sumS += bit[idx] * type;
  else
    sumT -= bit[idx] * type;
}

signed main()
{
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q >> s >> t;

  int bfr = 0, cur = 0;

  for (int i = 0; i <= n; i++)
  {
    cin >> cur;
    if (i == 0)
    {
      bfr = cur;
      continue;
    }

    bit[i] = cur - bfr;
    // cout << ": " << bit[i] << '\n';
    updSum(i, 1);

    bfr = cur;
  }

  while (q--)
  {
    // cout << ":: " << sumS << ' ' << sumT << '\n';
    int l, r, x;
    cin >> l >> r >> x;

    updSum(l, -1);
    if(r + 1 <= n)
    updSum(r + 1, -1);

    bit[l] += x;
    bit[r + 1] -= x;

    updSum(l, 1);
    if(r + 1 <= n)
    updSum(r + 1, 1);

    cout << -sumS * s + sumT * t << '\n';
  }
}

/*
0 4 1 8
  4 -3 7
sumS = 11
sumT = 3

0 6 3 8
  6 -3 5
 - 6 x 1 + 3 x 2 - 5 x 1  = -5


0 4 3 8
  4 -1 5
- 4 x 1 + 1 x 2 - 5 x 1 = -7

0 4 8 13
*/

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