Submission #541393

#	Time	Username	Problem	Language	Result	Execution time	Memory
541393		Dec0Dedd	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	400 ms	15692 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXN = 2e5+1;
const int TSIZE = 1 << 20;

ll T[TSIZE], a[MAXN], ans, n, q, s, t;

void build(int v, int l, int r) {
   if (l == r) {
      T[v]=a[l];
      return;
   }

   int m=(l+r)/2;
   build(2*v, l, m), build(2*v+1, m+1, r);
}

void update(int v, int l, int r, int ql, int qr, ll x) {
   if (l > qr || r < ql) return;
   if (l >= ql && r <= qr) {
      T[v]+=x;
      return;
   }
   int m=(l+r)/2;
   update(2*v, l, m, ql, qr, x), update(2*v+1, m+1, r, ql, qr, x);
}

ll query(int v, int l, int r, int p, ll c) {
   if (l == r) return T[v]+c;
   int m=(l+r)/2;
   if (p <= m) return query(2*v, l, m, p, c+T[v]);
   return query(2*v+1, m+1, r, p, c+T[v]);
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   cin>>n>>q>>s>>t>>a[0];
   for (int i=1; i<=n; ++i) cin>>a[i];
   build(1, 0, n);
   for (int i=0; i<n; ++i) {
      if (a[i+1] > a[i]) ans-=s*(a[i+1]-a[i]);
      else ans+=t*(a[i]-a[i+1]);
   }

   for (int i=1; i<=q; ++i) {
      ll l, r, x;
      cin>>l>>r>>x;
      ll la=query(1, 0, n, l, 0), lla=query(1, 0, n, l-1, 0);
      if (la > lla) ans+=s*(la-lla);
      else ans-=t*(lla-la);

      if (r < n) {
         ll ra=query(1, 0, n, r, 0), rra=query(1, 0, n, r+1, 0);
         if (rra > ra) ans+=s*(rra-ra);
         else ans-=t*(ra-rra);
         update(1, 0, n, l, r, x);

         ra=query(1, 0, n, r, 0), rra=query(1, 0, n, r+1, 0);
         if (rra > ra) ans-=s*(rra-ra);
         else ans+=t*(ra-rra);
      } else update(1, 0, n, l, r, x);
      la=query(1, 0, n, l, 0), lla=query(1, 0, n, l-1, 0);

      if (la > lla) ans-=s*(la-lla);
      else ans+=t*(lla-la);
      cout<<ans<<"\n";
   }
}

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