제출 #1307010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307010		mikasa	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	621 ms	18228 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end()
#define pb push_back 
  
const int N=2e6+5;
const int mod=1e9+7;
const int inf=2e9;

struct Segtree {
  vector<int> tr;
  vector<int> lz;

  int n;

  void init(int n) {
    tr.assign(4*n+1,0);
    lz.assign(4*n+1,0);
    this->n=n;
  }

  void push(int u,int l,int r) {
    tr[u]+=(r-l+1)*lz[u];
    if (l!=r) {
      lz[u<<1]+=lz[u];
      lz[u<<1|1]+=lz[u];
    }
    lz[u]=0;
  } 

  void upd(int u,int l,int r,int x,int y,int k) {
    push(u,l,r);
    if (x>r||y<l) return;
    if (l>=x&&r<=y) {
      lz[u]+=k;
      push(u,l,r);
      return;
    }
    int m=l+r>>1;
    upd(u<<1,l,m,x,y,k);
    upd(u<<1|1,m+1,r,x,y,k);
    tr[u]=tr[u<<1]+tr[u<<1|1];
  }
  int get(int u,int l,int r,int x,int y) {
    push(u,l,r);
    if (x>r||y<l) return 0;
    if (l>=x&&r<=y) {
      return tr[u];
    }
    int m=l+r>>1;
    int q1=get(u<<1,l,m,x,y);
    int q2=get(u<<1|1,m+1,r,x,y);
    return q1+q2;
  }
  int at(int pos) {
    return get(1,0,n,pos,pos);
  }
};

int a[N];
void levi() {
  int n,q,s,t;
  cin>>n>>q>>s>>t;
  Segtree se;
  se.init(n);
  for (int i=1;i<=n+1;++i) {
    cin>>a[i-1];
    se.upd(1,0,n,i-1,i-1,a[i-1]);
  }
  int res=0;
  for (int i=1;i<=n;++i) {
    int diff=abs(a[i]-a[i-1]);
    if (a[i-1]<a[i]) res-=s*diff;
    else res+=t*diff;
  }
  //cout<<res<<'\n';
  for (int i=1;i<=q;++i) {
    int l,r,x;
    cin>>l>>r>>x;
    int diff=se.at(l-1)-se.at(l);
    int fa=(diff<0)?s*abs(diff):-t*abs(diff),re=0;
    if (r!=n) {
      int diff2=(se.at(r)-se.at(r+1));
      re=(diff2<0)?s*abs(diff2):-t*abs(diff2);
    }
    se.upd(1,0,n,l,r,x);
    res+=re+fa;
    diff=se.at(l-1)-se.at(l);
    if (diff<0) res-=s*abs(diff);
    else res+=t*diff;
    if (r!=n) {
      diff=se.at(r)-se.at(r+1);
      if(diff<0){
        res-=s*abs(diff);
      }
      else res+=t*diff;
    }
    cout<<res<<'\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while(tt--)levi();
}

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