제출 #782406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782406		kebine	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	710 ms	25672 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, s, t;
vector<int> a, tr, tr_bocil, bocil;
void build(int pos=0, int l=0, int r=n) {
  if(l==r) {tr_bocil[pos]=bocil[l]; tr[pos]=a[r]; return;}
  int mid=l+r>>1;
  build(2*pos+1, l, mid);
  build(2*pos+2, mid+1, r);
}
void push(int pos) {
  tr_bocil[2*pos+1]+=tr_bocil[pos];
  tr_bocil[2*pos+2]+=tr_bocil[pos];
  tr_bocil[pos]=0;
  tr[2*pos+1]+=tr[pos];
  tr[2*pos+2]+=tr[pos];
  tr[pos]=0;
}
int get_bocil(int idx, int pos=0, int l=0, int r=n) {
  if(l==r) return tr_bocil[pos];
  push(pos); int mid=l+r>>1;
  if(idx<=mid) return get_bocil(idx, 2*pos+1, l, mid);
  return get_bocil(idx, 2*pos+2, mid+1, r);
}
void update_bocil(int inc, int ll, int rr, int pos=0, int l=0, int r=n) {
  if(ll>rr || l>rr || ll>r) return;
  if(ll==l && rr==r) {tr_bocil[pos]+=inc; return;}
  push(pos); int mid=l+r>>1;
  update_bocil(inc, ll, min(rr, mid), 2*pos+1, l, mid);
  update_bocil(inc, max(mid+1, ll), rr, 2*pos+2, mid+1, r);
}
int get(int idx, int pos=0, int l=0, int r=n) {
  if(l==r) return tr[pos];
  push(pos); int mid=l+r>>1;
  if(idx<=mid) return get(idx, 2*pos+1, l, mid);
  return get(idx, 2*pos+2, mid+1, r);
}
void update(int inc, int ll, int rr, int pos=0, int l=0, int r=n) {
  if(ll>rr || l>rr || ll>r) return;
  if(ll==l && rr==r) {tr[pos]+=inc; return;}
  push(pos); int mid=l+r>>1;
  update(inc, ll, min(rr, mid), 2*pos+1, l, mid);
  update(inc, max(mid+1, ll), rr, 2*pos+2, mid+1, r);
}
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> q >> s >> t;
  a.resize(n+1); bocil.resize(n+1);
  tr_bocil.resize(n+1 << 2); tr.resize(n+1 << 2);
  for(int &p : a) cin >> p;
  for(int i=1; i<=n; i++) {
    if(a[i-1]<a[i]) bocil[i]=bocil[i-1]-s*(a[i]-a[i-1]);
    else bocil[i]=bocil[i-1]+t*(a[i-1]-a[i]);}
  build();
  while(q--) {
    int l, r, x; cin >> l >> r >> x;
    int l_bef=get_bocil(l);
    int B=get(l-1), A=get(l)+x;
    int now; if(B<A) now=get_bocil(l-1)-s*(A-B);
    else now=get_bocil(l-1)+t*(B-A);
    update_bocil(now-l_bef, l, r);
    update(x, l, r);
    if(r<n) {
      l_bef=get_bocil(r+1);
      B=get(r); A=get(r+1);
      if(B<A) now=get_bocil(r)-s*(A-B);
      else now=get_bocil(r)+t*(B-A);
      update_bocil(now-l_bef, r+1, n);
    }
    cout << get_bocil(n) << '\n';
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

foehn_phenomena.cpp: In function 'void build(long long int, long long int, long long int)':
foehn_phenomena.cpp:8:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |   int mid=l+r>>1;
      |           ~^~
foehn_phenomena.cpp: In function 'long long int get_bocil(long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   push(pos); int mid=l+r>>1;
      |                      ~^~
foehn_phenomena.cpp: In function 'void update_bocil(long long int, long long int, long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:29:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   push(pos); int mid=l+r>>1;
      |                      ~^~
foehn_phenomena.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   push(pos); int mid=l+r>>1;
      |                      ~^~
foehn_phenomena.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
foehn_phenomena.cpp:42:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   push(pos); int mid=l+r>>1;
      |                      ~^~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:50:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   50 |   tr_bocil.resize(n+1 << 2); tr.resize(n+1 << 2);
      |                   ~^~
foehn_phenomena.cpp:50:41: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   50 |   tr_bocil.resize(n+1 << 2); tr.resize(n+1 << 2);
      |                                        ~^~

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