Submission #783596

#	Time	Username	Problem	Language	Result	Execution time	Memory
783596		makanhulia	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	370 ms	17144 KiB

foehn_phenomena

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

# define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int n, q, s, t; 
int all[cnst]; 
int arr[cnst];
int posi[cnst*4];
int lazy[cnst*4];

int merge(int a, int b) {
  return a+b;
}

void build(int a, int b, int id) {
  if(a == b) {
    if(arr[a] < 0) posi[id] = s*abs(arr[a]);
    else posi[id] = t*abs(arr[a]);
    return;
  }
  int mid = (a+b)/2;
  build(a, mid, id*2);
  build(mid+1, b, id*2+1);
  posi[id] = merge(posi[id*2], posi[id*2+1]);
}

void update(int a, int b, int id, int pos, int val) {
  if(pos > b || pos < a) return;
  // cerr << a << " " << b << " " << id << " " << pos << " " << val << endl;
  if(a == pos && b == pos) {
    if(arr[a] < 0) posi[id] = s*abs(arr[a]);
    else posi[id] = t*abs(arr[a]);
    return;
  }
  int mid =(a+b)/2;
  if(pos <= mid) update(a, mid, id*2, pos, val);
  else update(mid+1, b, id*2+1, pos, val);
  posi[id] = merge(posi[id*2], posi[id*2+1]);
}

int get(int a, int b, int id, int from, int to) {
  if(to < a || from > b) return 0;
  if(from <= a && b <= to) return posi[id];
  int mid = (a+b)/2;
  return merge(get(a, mid, id*2, from, to), get(mid+1, b, id*2+1, from, to));
}


void solve() {
  cin >> n >> q >> s >> t; s *= -1;

  // all[0] = 0;

  for(int i = 0 ; i<=n; i++) cin >> all[i];
  for(int i = 1; i<=n; i++) arr[i] = all[i-1]-all[i];

  build(1, n, 1);
  // cerr << get(1, n, 1, 1, n) << endl;
  // for(int i = 1; i<=n; i++) cerr << arr[i] << " "; cerr << endl;
  // for(int i = 1; i<=n; i++) cerr << get(1, n, 1, i, i) << " "; cerr << endl; cerr << endl;

  while(q--) {
    int x, y, z; cin >> x >> y >> z;
    arr[x] -= z;
    arr[y+1] += z;

    update(1, n, 1, x, 0);
    // update(1, n, 1, y, 0);
    update(1, n, 1, y+1, 0);

    // for(int i = 1; i<=n; i++) cerr << arr[i] << " "; cerr << endl;
    // for(int i = 1; i<=n; i++) cerr << get(1, n, 1, i, i) << " "; cerr << endl; cerr << endl;

    cout << get(1, n, 1, 1, n) << endl;
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  int t = 1;
  if(mutipletestcase) cin >> t; 
  while(t--) solve();
}

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